Swap indices and values

Question

The task

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
[4]           [{},{},{},{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 code-golf challenge, shorter is better.

Answer 1

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 {[1]; [2]; [3]}).

Try it online! Or verify all test cases.

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.

Answer 2

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.

Answer 3

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.

Answer 4

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 ^^         [[[],[],[],[],[],[1]],
          as many times as           [[],[],[],[],[],[2]],
          each of ^                  [[],[],[],[3]],
                                     [[],[],[],[4]]]
       /  reduce by...
     ;"   vectorized concatenation  [[],[],[],[3,4],[],[1,2]]

Answer 5

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.

Answer 6

Haskell, 45 bytes

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.

Answer 7

PHP, 55 bytes

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

0-indexed.

Answer 8

R, 68 49 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.

Answer 9

Python 2, 91 86 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!

Answer 10

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:
 +        -   addition                    [0,0,0,1,1,2]
    Ġ     - 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]]

Answer 11

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([3]))
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`|`

Answer 12

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

Answer 13

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!

Answer 14

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!

Answer 15

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}

Answer 16

05AB1E, 10 bytes

ZFā¹N-ψ}¯

Try it online!

Answer 17

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.

Answer 18

PowerShell, 81 bytes

$args[0]|%{if($_-gt($c=$r.count)){$r+=@($t)*($_-$c)}$r[--$_]+=,++$i};$r|%{"{$_}"}

Try it online!

1-indexed.

Answer 19

GNU Make, 214 213 208 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).

Answer 20

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!

Answer 21

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