29
\$\begingroup\$

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 challenge, shorter is better.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user62131 May 9 '17 at 22:04
  • \$\begingroup\$ 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? \$\endgroup\$ – Leaky Nun May 10 '17 at 1:44
  • 1
    \$\begingroup\$ @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}]. \$\endgroup\$ – ngenisis May 10 '17 at 2:51
  • \$\begingroup\$ 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]? \$\endgroup\$ – Skidsdev May 10 '17 at 9:45
  • \$\begingroup\$ @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.) \$\endgroup\$ – user62131 May 11 '17 at 11:33

21 Answers 21

9
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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]]
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 36 bytes

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

Explanation

enter image description here

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

PHP, 55 bytes

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

0-indexed.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Out-golfed again by a nested list comprehension. :D \$\endgroup\$ – totallyhuman May 9 '17 at 23:51
2
\$\begingroup\$

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]]
\$\endgroup\$
2
\$\begingroup\$

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`|`
\$\endgroup\$
  • \$\begingroup\$ Wow. I'm so confused how `{${o.join`},{`}}` is legal ES2015. \$\endgroup\$ – Steve Bennett May 10 '17 at 5:53
  • \$\begingroup\$ @SteveBennett, it's a template literal. In older versions of JS it would be "{" + o.join("},{") + "}", if that makes it any clearer. \$\endgroup\$ – Shaggy May 10 '17 at 14:45
  • \$\begingroup\$ 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? \$\endgroup\$ – Steve Bennett May 11 '17 at 6:50
  • \$\begingroup\$ Hmm, ok, so in this context join` is equivalent to join('. Had no idea you could do that. \$\endgroup\$ – Steve Bennett May 11 '17 at 7:01
  • \$\begingroup\$ 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. :) \$\endgroup\$ – Steve Bennett May 11 '17 at 7:08
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – ngenisis May 10 '17 at 3:14
1
\$\begingroup\$

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}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 10 bytes

ZFā¹N-ψ}¯

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

PowerShell, 81 bytes

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

Try it online!

1-indexed.

\$\endgroup\$
0
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user62131 May 13 '17 at 23:20
  • \$\begingroup\$ @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. \$\endgroup\$ – eush77 May 14 '17 at 5:19
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy