# Swap indices and values

Write a program or function whose input is a list/array X of integers, and whose output is a list of sets of integers Y, such that for each element e in each set Y[i], X[e] = i, and such that the total number of elements in the sets in Y equals the number of elements in X.

(This is basically the same operation as reversing a hashtable/dictionary, except applied to arrays instead.)

# Examples

These examples assume 1-based indexing, but you can use 0-based indexing instead if you prefer.

X             Y
           [{},{},{},{1}]
[1,2,3]       [{1},{2},{3}]
[2,2,2]       [{},{1,2,3}]
[5,5,6,6]     [{},{},{},{},{1,2},{3,4}]
[6,6,5,5]     [{},{},{},{},{3,4},{1,2}]


# Clarifications

• You may represent a set as a list, if you wish. If you do so, the order of its elements does not matter, but you may not repeat elements.
• You can use any reasonable unambiguous I/O format; for example, you could separate elements of a set with spaces, and the sets themselves with newlines.
• Y should be finitely long, and at least long enough to have all elements of X as array indexes. It may, however, be longer than the maximal element of X (the extra elements would be empty sets).
• The elements of X will all be valid array indices, i.e. non-negative integers if you use 0-based indexing, or positive integers if you use 1-based indexing.

# Victory condition

As a challenge, shorter is better.

• Related. In the Sandbox post (now deleted, but you can view it if you have the reputation), we decided it probably wasn't a duplicate, but feel free to vote to close if you disagree.
– user62131
May 9, 2017 at 22:04
• Does "the order of its elements does not matter" mean that the outputs of [5,5,6,6] and [6,6,5,5] can be identical? May 10, 2017 at 1:44
• @LeakyNun The order of the elements of the sets in the output list doesn't matter. So [5,5,6,6] and [6,6,5,5] can't have identical output, but the output for [5,5,6,6] could also have been, e.g., [{},{},{},{},{2,1},{4,3}].
– user61980
May 10, 2017 at 2:51
• Is there an assumable max value of an index in X? Also can empty sets have a 0 in them instead of being actually empty? For example would [{0},{0},{0},{0},{1,2},{3,4}] be valid output for [5,5,6,6]? May 10, 2017 at 9:45
• @Mayube: No to the first answer (although if you're using a language which has limited range on integers, you can write the program as though integers could be unboundedly large, and not worry about it breaking if someone gives you an out-of-range integer as input). With respect to the second question, that's an unambiguous (if weird) syntax when you're using 1-based indexing, so yes in that case (obviously, no if you're using 0-based indexing because then the 0 would mean someting else.)
– user62131
May 11, 2017 at 11:33

# MATL, 8 bytes

tn:IXQ&D


Input is a column vector, with ; as separator (for example [2;2;2]). Output is the string representation of a cell array of row vectors (for example {[]; [1 2 3]}). A row vector of a single element is the same as a number (so {1; 2; 3} would be output instead of {; ; }).

### Explanation

t     % Implicit input, say x. Duplicate
n     % Number of elements, say N
:     % Range: [1 2 ... N]
IXQ   % accumarray(x, [1 2 ... N], [], @(x){sort(x).'})
&D    % String representation


Most of the work is done by Matlab's higher-order function accumarray, which groups elements in the second input according to matching values in the first, and applies a specified function to each group. The function in this case is @(x){sort(x).'}, which outputs the sorted elements in each group and causes the results for all groups to be packed in a cell array.

# Python, 69 bytes

lambda s:[[j for j,x in enumerate(s)if x==i]for i in range(max(s)+1)]


Uses 0-based indexing.

# Jelly, 7 5 bytes

=þṀT€


Try it online!

### How it works

=þṀT€  Main link. Argument: A (array)

Ṁ    Yield m, the maximum of A.
=þ     Equals table; for each t in [1, ..., m], compare all elemnts of A with t,
yielding a 2D Boolean array.
T€  Truth each; for each Boolean array, yield all indices of 1.


# Jelly, 8 bytes

Jẋ"Ṭ€;"/


Try it online!

## How it works

Jẋ"Ṭ€;"/  argument: z           eg. [6,6,4,4]
J         [1 .. len(z)]             [1,2,3,4]
Ṭ€     untruth each of z         [[0,0,0,0,0,1],
[0,0,0,0,0,1],
[0,0,0,1],
[0,0,0,1]]
ẋ"       repeat each of ^^         [[[],[],[],[],[],],
as many times as           [[],[],[],[],[],],
each of ^                  [[],[],[],],
[[],[],[],]]
/  reduce by...
;"   vectorized concatenation  [[],[],[],[3,4],[],[1,2]]


## Mathematica, 36 bytes

Join@@@#~Position~n~Table~{n,Max@#}&


## Explanation For each n in {1, 2, ..., Max@#}, where Max@# is the largest integer in the input list, computes the Positions where n appears in the input list #. Since Position[{6,6,5,5},5] (for example) returns {{3},{4}}, we then Apply Join to all elements at level {1} of the result.

s takes a list of integers and returns a list of lists. 1-indexed to keep the test case inputs unmodified (although the output gets some extra empty lists).

s l=[[i|(i,y)<-zip[1..]l,y==x]|x<-[1..sum l]]


Try it online!

These are pretty straightforward nested list comprehensions. The only slight tweak is taking advantage of the option to make a longer list by using sum instead of maximum.

# PHP, 55 bytes

<?while($i<=max($_GET))print_r(array_keys($_GET,$i++));


0-indexed.

# R, 6849 47 bytes

lapply(1:max(x<-scan()),function(y)which(y==x))


Surprisingly, a lot more straightforward than the longer solutions. Takes a vector x from STDIN, creates a vector from 1 to max(x), implicitly generates a list of length max(x), and checks which indices in x correspond with those in the new list. Implicitly prints output.

## Older version:

o=vector('list',max(x<-scan()));for(i in x)o[[i]]=c(o[[i]],F<-F+1);o


Slightly different approach to the other R answer. Takes a vector to STDIN, creates a list with length equal to the maximum value in the input. Loops over the input and adds the index into the right place.

Uses 1-based indexing.

# Python 2, 9186 85 bytes

I am programming on my phone but I really liked this challenge. I can most definitely golf this further.

def f(a):
r=[[]for i in range(max(a)+1)]
for i,j in enumerate(a):r[j]+=[i]
print r


Try it online!

• Out-golfed again by a nested list comprehension. :D May 9, 2017 at 23:51

# Jelly, 9 bytes

Ṭ+\ịĠȧ@"Ṭ


1-indexed, empty sets represented as 0, sets of one item represented as N sets of multiple items represented as [M,N,...]

Try it online!

### How?

Ṭ+\ịĠȧ@"Ṭ - Main link: list a        e.g. [6,6,4,4]
Ṭ         - untruth a                     [0,0,0,1,0,1]
\       - cumulative reduce with:
Ġ     - group indices of a by value   [[3,4],[1,2]]
ị      - index into                    [[1,2],[1,2],[1,2],[3,4],[3,4],[1,2]]
Ṭ - untruth a                     [0,0,0,1,0,1]
"  - zip with:
ȧ@   -   and with reversed @rguments [0,0,0,[3,4],0,[1,2]]


## JavaScript (ES6), 64 62 bytes

Saved 2 bytes thanks to @SteveBennett

Takes 0-indexed input. Returns a comma-separated list of sets.

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&{${o.join},{}}  ### Test cases let f = a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&{${o.join},{}}

console.log(f())
console.log(f([0,1,2]))
console.log(f([1,1,1]))
console.log(f([4,4,5,5]))
console.log(f([5,5,4,4]))

### Alternate version, 53 bytes

If a simplified output such as '||||3,2|1,0' is acceptable, we can just do:

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&o.join|

• Wow. I'm so confused how {${o.join},{}} is legal ES2015. May 10, 2017 at 5:53 • @SteveBennett, it's a template literal. In older versions of JS it would be "{" + o.join("},{") + "}", if that makes it any clearer. May 10, 2017 at 14:45 • No, I know about those - it's the backquote after the word join that confuses me. Is that closing the string (in which case wtf) or is that how you escape a close brace? May 11, 2017 at 6:50 • Hmm, ok, so in this context join is equivalent to join('. Had no idea you could do that. May 11, 2017 at 7:01 • Ah, now I see. It's a tagged template literal. Which you can abuse to save a couple of characters whenever calling a function that takes one string argument (and ignores others): array.join . Super confusing here because you're embedding that within a template string, and even more confusingly, the joining string is },{, which coincidentally looked like part of the template string...and is just weird and ugly anyway. :) May 11, 2017 at 7:08 # Bash, 109 bytes Too bad there is no built-in for array max value. a=($@)
for((x=m=1;x<=m;x++)){ for((y=0;y<$#;)){((m<a[y]))&&((m=a[y]));((a[y++]==x))&&printf "%d "$y;};echo;}


Try it online!

## Mathematica 62 bytes

(Y={}~Table~Max@#;Y[[#[[j]]]]~AppendTo~j~Table~{j,Tr[1^#]};Y)&


I'll run it for you

(Y={}~Table~Max@#;Y[[#[[j]]]]~AppendTo~j~Table~{j,Tr[1^#]};Y)&[{4,5,2,3,3,8,6,3}]


{{}, {3}, {4, 5, 8}, {1}, {2}, {7}, {}, {6}}

Try it online (just paste the code with ctrl-v and press shift+enter)
don't forget to paste the input list at the end like in the example above

• Welcome to PPCG! You can save a byte by using infix notation for AppendTo. Also, {j,1,Length[#1]} could just be {j,Length@#}, or even shorter, {j,Tr[1^#]}. Tr[1^#] is a pretty common trick to save a byte over using Length.
– user61980
May 10, 2017 at 3:14

# Perl 6,  36 32  29 bytes

->\a{map {a.grep(*==$_):k},1..a.max}  Try it {map {.grep(*==$^a):k},1.. .max}


Try it

{map {.grep($^a):k},1.. .max}  Try it ## Expanded: { # bare block lambda with implicit parameter ｢$_｣

map

{  # bare block lambda with placeholder parameter ｢$a｣ .grep( # grep for the values in ｢$_｣
$^a # that are equal to the currently tested value (and declare param) ) :k # return the key (index) rather than the value }, 1 .. .max # Range from 1 to the maximum value in ｢$_｣

}


Returns zero based indexes, to get 1 based use cross operator (X) combined with + op. (33 bytes)

{1 X+.grep($^a):k}  To get it to return Sets just add set in there (total 37 bytes) {set 1 X+.grep($^a):k}


# Röda, 51 bytes

f s{seq(1,max(s))|[[s()|enum|[_2+1]if[_1=i]]]for i}


It's a port of the Python answer by Uriel.

Another version (88 bytes):

f a{I=indexOf;seq(1,max(a))|{|i|b=a[:]c=[]x=1{c+=x+I(i,b)b-=i;x++}until[I(i,b)<0];[c]}_}


Try it online!

Both a 1-indexed.

# R, 80 72 bytes

1-indexed, takes X from stdin. Returns a list of vectors of the indices, with NULL as the empty set.

X=scan();Y=vector('list',max(X));Y[X]=lapply(X,function(x)which(X==x));Y


Try it online!

old version:

X=scan();Y=vector('list',max(X));for(i in 1:length(X))Y[[X[i]]]=c(Y[[X[i]]],i);Y


Try it online!

• I think that Y=list(); works just as well May 11, 2017 at 7:36
• Managed to shave off a few bytes in my answer :) codegolf.stackexchange.com/a/120024/59530
May 11, 2017 at 8:09

$args|%{if($_-gt($c=$r.count)){$r+=@($t)*($_-$c)}$r[--$_]+=,++$i};$r|%{"{$_}"}  1-indexed. # GNU Make, 214213208 204 bytes X=$(MAKECMDGOALS)
M=0
P=$(eval N=$(word $1,$X))$(if$N,$(if$(shell dc -e$Nd$Mds.\>.p),$(eval M=$N),)$(eval A$N+=$1$(call $0,$(shell expr $1 + 1))),)$(call P,1)$(foreach K,$(shell seq $M),$(info $(A$K)))


I/O: input array via arguments, output to stdout, one per line, separated by spaces.

$make -f swap.mk 2 2 2 3 2 1 make: *** No rule to make target 2'. Stop.  ## Explanation X=$(MAKECMDGOALS)     # Input array
M=0                   # Max value encountered in X
P=$(eval N=$(word $1,$X))  # Get next word from X
$(if$N,$(if$(shell dc -e$Nd$Mds.\>.p),
$(eval M=$N),)    # Update M
$(eval A$N+=$1 # Append index to a variable named after value$(call $0, # Recurse (call returns empty string)$(shell expr $1 + 1))),)$(call P,1)           # Initial call to P. 1 is the first index
$(foreach K, # Print all values of A* variables$(shell seq $M),$(info $(A$K)))     # Uninitialized ones default to empty strings


The order of indices in sets is reversed because P calls itself recursively before updating A$2 (call executed in the evaluation of the right-hand side). • Does make have any way to do arithmetic itself? Calling into external programs to do it feels a bit like cheating, because you could probably put much more of the algorithm into those programs and end up with a shorter program. – user62131 May 13, 2017 at 23:20 • @ais523 It has not. Previous version used bc and grep. I could also use test and $?. dc has a terser syntax, but frankly all of these feel the same. May 14, 2017 at 5:19

# 05AB1E, 10 bytes

ZFā¹N-Ïˆ}¯


Try it online!

# Common Lisp, 91 bytes

(lambda(x &aux(l(make-list(eval(max,@x))))(i 0))(dolist(y x l)(push(incf i)(nth(1- y)l))))


1-based indexing, returns the sets as lists.

Try it online!

# k, 13 bytes

{(=x)@!1+|/x}


This is 0-indexed.

Try it online!

{           } /function(x)
(=x)         /make a map/dictionary of values to their indices
|/x  /get maximum value in x
!1+     /make a range from 0 to the value, inclusive
@        /get map value at each of the values in the range
/    0N is given where there is no result


# Uiua, 6 bytes

⊕□∶⇡⧻.


Try it!

0-indexed.

⊕□∶⇡⧻.
.  # duplicate
⧻   # length
⇡    # range
∶     # swap
⊕□      # group by box


# Japt, 7 bytes

Output is 0-based.

rÔõ@ð¶X


Try it

# Vyxal, 38 bitsv2, 4.75 bytes

Gǒ=vT


Try it Online!

Bitstring:

01011011100001100011111110111100010001


Exact same algorithm as Jelly, independently discovered.

## Explained

Gǒ=vT­⁡​‎⁪⁪⁠‎⁪⁡⁪⁠⁪⁢⁪‏⁠⁪⁪‏​⁡⁠⁡‌⁢​‎⁪⁪‏​⁢⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁡⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁣⁪‏‏​⁡⁠⁡‌⁢⁡​‎⁪⁪⁠⁪⁪‏​⁢⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏‏​⁡⁠⁡‌­
ǒ     # ‎⁡Reduce pairs in the cartesian product of
# ‎⁢the input
G      # ‎⁣and the maximum of the input
=    # ‎⁤by equality
# ‎⁢⁡This creates a list of [1s in places where input == x for x in range(max(input))]
vT  # ‎⁢⁢Get the indices of those 1s for each list
💎


Created with the help of Luminespire.

# JavaScript (Node.js), 73 bytes

x=>x.map((n,i)=>A[(g=n=>n&&g(n-1,A[n]=A[n]||[]))(n),n].push(i),A=[[]])&&A
`

Try it online!