Enumerate an array, grouping duplicates

Question

The objective of this challenge is to take an array of positive integers, and enumerate its indices, grouping like elements.

An enumeration without any duplicates is done by just outputting an array of pairs (value, index), for example, [3, 4, 13, 9, 2] => [[3,1],[4,2],[13,3],[9,4],[2,5]].

However, if a given element appears a second time, it isn't given its own pair, but is instead added to the group of its first occurrence. If in our above example we replaced the 9 with 3, then in the output we would remove [9,4] and replace [3,1] with [3,1,4].

In the output, groups must be ordered by their first occurrence, and indices must be in ascending order. The element must be first in a group, before its indices. Output may be 0 or 1 indexed. You may assume the array has at least one element.

Test cases:

Input | Output (One-indexed)
[3, 2, 2, 3] | [[3, 1, 4], [2, 2, 3]]
[17] | [[17, 1]]
[1, 1] | [[1, 1, 2]]
[1, 1, 2] | [[1, 1, 2], [2, 3]]
[1, 2, 3, 4] | [[1, 1], [2, 2], [3, 3], [4, 4]]
[1, 1, 1, 1] | [[1, 1, 2, 3, 4]]

This is code-golf, fewest bytes wins!

• Shaggy: Would it be acceptable for the indides to be output as strings, e.g. [[17,"1"]]? (Don't know yet if I can save any bytes that way, still working on it!)
• Pavel: @shaggy sure, that's fine
• totallyhuman: Possible duplicate.
• Conor O'Brien: Can we output something like [[3, [1, 4]], [2, [2, 3]]] instead?
• Conor O'Brien: @Pavel that's no reason :p but sure

Answer 1

Dyalog APL, 5 bytes

(⊂,)⌸

Try it online!

,⌸ for 2 bytes almost works, but has trailing zeroes :/

• Mr. Xcoder: What in the world does ⌸ do?
• dzaima: @Mr.Xcoder gets the indexes of each thing and calls the left operator with the thing and indices where it exists
• Pavel: Since the isue with ,⌸ is trailing zeroes, and zeroes will never be in the input, would it be possible to drop all zeroes in less than 3 bytes?
• dzaima: @Pavel the reason that there are the zeroes is that the result is a matrix, which has to have exact dimensions, so there's only 1 byte for dropping the zeroes for any byte gain. I feel like this might be golfable though.
• Adám: "fancy af" array output format: Try it online!

Answer 2

J, 12 bytes

~.,&.><@I.@=

Zero-indexed.

Try it online!

If you can remove all of the work I'm doing with boxes, you can probably reduce the bytecount by quite a bit. I'm going to see if I can figure that out.

Explanation

This is probably too early to be explaining (there ought to be more golfs).

~. ,&.> <@I.@=
 = Self-classify (comparison of each unique element to array)
 @ Composed with
 I. Indices of ones (where it's equal)
 @ Composed with
 < Boxed (how we deal with arrays of unequal length)
 ,&.> Joined with
 > Unbox each
 , Concatenate
 &. Box again
~. Unique elements

• Pavel: That array output format is fancy af
• cole: @Pavel it's also taking a lot of bytes Π.Π

Answer 3

Python 3, (削除) 83 (削除ここまで) 82 bytes

^{-1 byte thanks to Mego}

lambda x:[[n]+[j for j,m in enumerate(x)if m==n]for n in sorted({*x},key=x.index)]

Try it online!

• user45941: j+1 -> j (indices may be zero-indexed)

Answer 4

05AB1E, 10 bytes

ÙεDIQƶ0K) ̃

Try it online!

Explanation

Ù # remove duplicates
 ε # apply to each element
 D # duplicate
 IQ # compare for equality with input
 ƶ # multiply each element by its index (1-based)
 0K # remove zeroes
 ) ̃ # wrap in a flattened list

Answer 5

Haskell, 48 bytes

import Data.List
f l=nub[k:elemIndices k l|k<-l]

Try it online!

Answer 6

Attache, 15 bytes

Flat=>Positions

Try it online!

This is an interesting case of =>, the operator form of Map. When given two functional arguments f and g, Map returns a function f => g[x] over x. That is, the RHS is applied to the input, then the LHS is mapped.

The builtin Positions generates an array representing the grouping of entries by indices. By default, when not supplied with a second argument, Positions will use the first argument. Flat is then mapped over each item, as that is what the question requires.

Alternative solutions

31 bytes

MapArgs[Concat#~Indices,Unique]

Try it online!

A pretty short, builtin-less alternative. MapArgs is a function like Map, except you can feed extra arguments into it. For example, MapArgs[{_1 + _2}, 1..3, 3] is [4, 5, 6]. Like Map, it becomes curried when supplied with two functional arguments. The function be mapped is Concat#~Indices, which is a fork. This fork is applied to the Unique items of the input and the input itself. This translates to Concat[_, Indices[_2, _]] (with the arguments of Indices swapped through ~), which pairs the element being mapped (_) with the indices of said element _ in the input array, which is _2 (as ffed through MapArgs).

43 bytes

{Flat=>Zip[Unique[_],Indices[_,Unique[_]]]}

Try it online!

This is really just a more verbose (yet a tad more readable) combination of solutions #1 and #2.

Answer 7

Jelly, 6 bytes

Q;"ĠṢ$

Try it online!

Explanation:

Q;"ĠṢ$
Q Keep the first occurrence of each element
 $ Last two links as a monad
 Ġ Group indices of equal elements, then sort the resulting list of groups by the element they point to
 Ṣ Sort; used to re-order the list of groups based on first occurrence instead
 " Vectorize link between two arguments (the first occurrences and the group list)
 ; Concatenate

• Pavel: Doesn't work for the last test case. The array should be nested another layer, the output is alway two-dimensional.
• Erik the Outgolfer: @Pavel yes it does, I just forgot to add a footer (answer is a function)
• Pavel: Ok then, cool. Explanation soon, yes? :P
• Erik the Outgolfer: @Pavel added explanation

Answer 8

Pyth, 7 bytes

0-indexed.

{+VQxRQ

Try it here! Alternative.

How?

{+VQxRQ – Full program.
 RQ – For each element...
 x – Get all its indices.
 +V – And apply vectorised concatenation.
 Q – With the input.
{ – Deduplicate.

Answer 9

K (oK), 10 bytes

Solution:

(!x),'.x:=

Try it online!

Examples:

(!x),'.x:=,17
,17 0
(!x),'.x:=1 1
,1 1 2
(!x),'.x:=1 0 1
(1 1 2
2 3)
(!x),'.x:=1 2 3 4
(1 0
2 1
3 2
4 3)

Explanation:

Evaluation is performed right-to-left. I still think this is golf-able further...

(!x),'.x:= / the solution
 = / group input into dictionary, item!indices
 x: / save as variable x
 . / value of x (the indices)
 ,' / concatenate (,) each-both (') with
( ) / do this together
 !x / the key of x (i.e. the items)

Notes:

• 14 bytes without declaring x, (,/)'+(!;.)@'=, gave up with this approach...

• Adám: You may return 0-indexed result, so I think you can skip the 1+.

Answer 10

MATL, 8 bytes

u"@tG=fh

Try it at MATL Online

Explanation

 # Implicitly get the input
u # Compute the unique values
" # For each unique value, N
 @ # Push the value N to the stack
 t # Duplicate N
 G # Grab the input
 =f # Get the 1-based indices of the elements that equal N
 h # Horizontally concatenate N with the indices
 # Implicitly display the result

• Giuseppe: ooooohhh that's clever! I had like 18 bytes trying to use &f but never did get it to work.

Answer 11

Actually, 24 bytes

;;╗⌠╝╜r⌠╜E╛=⌡░⌡M@Z⌠♂i⌡M╔

Try it online!

Explanation:

;;╗⌠╝╜r⌠╜E╛=⌡░⌡M@Z⌠♂i⌡M╔
;; make two copies of input
 ╗ save a copy to register 0
 ⌠╝╜r⌠╜E╛=⌡░⌡M map over input:
 ╝ save the element in register 1
 ╜r indices for input
 ⌠╜E╛=⌡░ filter:
 ╜E element in input at index
 ╛= equals element for outer map (from register 1)
 @Z swap, zip input with map result
 ⌠♂i⌡M flatten each element in zipped list
 ╔ uniquify

Answer 12

Julia 0.6, 37 bytes

Thanks to Pavel for 1 byte off.

y->[[x;findin(y,[x])]for x=unique(y)]

Try it online!

• Pavel: Remove the space between ] and for for -1 byte.

Answer 13

R, 56 bytes

function(x)lapply(unique(x),function(y)c(y,which(x==y)))

Try it online!

---

This is my first attempt at codegolf, so any feedback is welcome!

• Pavel: Welcome to PPCG! Nice first answer.
• Giuseppe: Hey there Florian! Very nice answer. This is actually a snippet rather than a program or function -- it assumes the input is hardcoded into x, but there has to be a way of reading input -- typically we use scan or define a function. Additionally, it has to output, so'd have to wrap this in a print or a cat.
• Giuseppe: see this question for more handy R golfing tricks :)
• Florian: Thanks guys! And the link to the r tips is certainly useful!
• Giuseppe: @Florian R isn't so bad as you think (except on string challenges...) so long as you remember you're golfing against other R golfers! Feel free to ping me in chat if you have questions. There's a couple of R golfers who are active, and they'll definitely offer suggestions, and appreciate yours as well! Welcome to golfing :)

Answer 14

Wolfram Language (Mathematica), 40 bytes

Saved a byte thanks to Martin Ender.

KeyValueMap[{#,##&@@#2}&]@*PositionIndex

Try it online!

• Pavel: How does @*PositionIndex work?
• alephalpha: @Pavel @* is composition of functions. PositionIndex basically does all the job, but returns an association instead of a list.
• Martin Ender: {#,##&@@#2}& saves a byte.

Answer 15

JavaScript (ES6), 64 bytes

0 indexed

a=>a.map((v,i)=>a[-v]?a[-v].push(i):a[-v]=[v,i]).filter(x=>x[0])

Note, this assume input numbers being positive, so v > 0

Test slightly modified (1 indexed) to match the test cases

var F=
a=>a.map((v,i)=>a[-v]?a[-v].push(i+1):a[-v]=[v,i+1]).filter(x=>x[0])
test = [ // output 1 indexed
 [3, 2, 2, 3],// | [[3, 1, 4], [2, 2, 3]]
 [17], // | [[17, 1]]
 [1, 1], // | [[1, 1, 2]]
 [1, 1, 2], // | [[1, 1, 2], [2, 3]]
 [1, 2, 3, 4], // | [[1, 1], [2, 2], [3, 3], [4, 4]]
 [1, 1, 1, 1] // | [[1, 1, 2, 3, 4]] 
]
test.forEach(t => {
 x = F(t)
 console.log(JSON.stringify(t)+ ' -> ' + JSON.stringify(x))
})

Answer 16

APL NARS, 24 bytes, 12 chars

{∪⍵, ̈⍸ ̈⍵=⊂⍵}

-4 bytes thanks to Adam test:

 f←{∪⍵, ̈⍸ ̈⍵=⊂⍵}
 ⎕fmt f 3 2 2 3
┌2────────────────┐
│┌3─────┐ ┌3─────┐│
││ 3 1 4│ │ 2 2 3││
│└~─────┘ └~─────┘2
└∊────────────────┘
 ⎕fmt f 17
┌1──────┐
│┌2────┐│
││ 17 1││
│└~────┘2
└∊──────┘
 ⎕fmt f 1 1
┌1───────┐
│┌3─────┐│
││ 1 1 2││
│└~─────┘2
└∊───────┘
 ⎕fmt f 1 2 3 4
┌4──────────────────────────┐
│┌2───┐ ┌2───┐ ┌2───┐ ┌2───┐│
││ 1 1│ │ 2 2│ │ 3 3│ │ 4 4││
│└~───┘ └~───┘ └~───┘ └~───┘2
└∊──────────────────────────┘
 ⎕fmt f 1 1 1 1
┌1───────────┐
│┌5─────────┐│
││ 1 1 2 3 4││
│└~─────────┘2
└∊───────────┘

• Adám: Shave a 4 bytes/2 chars: {∪⍵,¨⍸¨⍵=⊂⍵}

Answer 17

SWI-Prolog, (削除) 165 (削除ここまで) 117 bytes

-48 bytes thanks to Prolog golfing tips.

h(I):-I+[]-1.
[H|T]+R-N:-(select([H|A],R,[H|L],S),!,append(A,[N],L);append(R,[[H,N]],S)),O is N+1,(T+S-O,!;write(S)).

Try it online!

Explanation

% The predicate that prints the grouped duplicates. It's a wrapper because we
% need some extra arguments to keep state:
enumerate_duplicates(Input) :- enumerate(Input, [], 1).
% In the golfed code, operators are used to represent this predicate.
% See https://codegolf.stackexchange.com/a/153160
% Go through the input, build up the result on the way and print it.
enumerate([Head|Tail], Result, Index) :-
 (
 % If our current Result already contains a list that starts with the
 % current first element in our input, Head, NewIndexes will become the
 % new "tail" of that list in our next result list:
 select([Head|OldIndexes], Result, [Head|NewIndexes], NextResult),
 % Don't backtrack before this if goals below this fail:
 !,
 % The as-yet-unknown NewIndexes above should in fact be the same as
 % OldIndexes with our current Index appended:
 append(OldIndexes, [Index], NewIndexes)
 % Use ; instead of separate predicate rules.
 % See https://codegolf.stackexchange.com/a/67032
 ;
 % If our current Result did not already contain Head, append a new list
 % for it with the current index:
 append(Result, [[Head, Index]], NextResult)
 ),
 % Increment our index counter:
 NextIndex is Index + 1,
 (
 % And continue with the rest of our input:
 enumerate(Tail, NextResult, NextIndex),
 % Don't backtrack if the above succeeded:
 !
 ;
 % If Tail is no longer a multi-element list, we're done. Print:
 write(NextResult)
 ).

Answer 18

JavaScript (ES6), 68 bytes

0-indexed.

a=>a.map(p=(x,i)=>1/p[x]?b[p[x]].push(i):b.push([x,p[x]=i]),b=[])&&b

Test cases

let f =
a=>a.map(p=(x,i)=>1/p[x]?b[p[x]].push(i):b.push([x,p[x]=i]),b=[])&&b
console.log(JSON.stringify(f([3, 4, 13, 9, 2]))) // [[3,0],[4,1],[13,2],[9,3],[2,4]]
console.log(JSON.stringify(f([3, 4, 13, 3, 2]))) // [[3,0,3],[4,1],[13,2],[2,4]]
console.log(JSON.stringify(f([3, 2, 2, 3] ))) // [[3,0,3],[2,1,2]]
console.log(JSON.stringify(f([17] ))) // [[17,0]]
console.log(JSON.stringify(f([1, 1] ))) // [[1,0,1]]
console.log(JSON.stringify(f([1, 1, 2] ))) // [[1,0,1],[2,2]]
console.log(JSON.stringify(f([1, 2, 3, 4] ))) // [[1,0],[2,1],[3,2],[4,3]]
console.log(JSON.stringify(f([1, 1, 1, 1] ))) // [[1,0,1,2,3]]

• edc65: Input numbers are != 0, that could be useful to avoid the 1/x trick

Answer 19

PHP 4.1, 88 bytes

Yeah, it is pretty long.

This assumes a default php.ini file (short_open_tag = On and register_globals = On).

<?foreach($A as$k=>$v){!$b[$v]&&$b[$v]=array($v);$b[$v][]=$k;}print_r(array_values($b));

This presents the array in an human-readable way.
The values can be passed by POST, GET and COOKIE, inside the key "A".

---

For a modern version, one can use (90 bytes):

<?foreach($_GET[A]as$k=>$v){if(!$b[$v])$b[$v]=[$v];$b[$v][]=$k;}print_r(array_values($b));

The result is the same, except all values have to be passed over GET parameters inside the key "A".

Answer 20

Perl 6, (削除) 63 (削除ここまで) 61 bytes

*.pairs.classify(*.value).map({.key,|.value».key}).sort(*.[1])

Test it (0-based)

{sort *.[1],map {.key,|.value».key},classify *.value,.pairs}

Test it (0-based same algorithm)

Expanded:

# WhateverCode lambda (this is the parameter) 
*\ # [3,2,2,3]
# get a list of Pairs (zero based index => value)
.pairs # (0=>3,1=>2,2=>2,3=>3)
# classify based on the values (unordered result)
.classify(*.value) # {2=>[1=>2,2=>2],3=>[0=>3,3=>3]}
# simplify the structure
.map({
 .key, # the value
 |.value».key # slip in the indexes
}) # ((3,0,3),(2,1,2))
# sort based on first index
.sort(*.[1])

Answer 21

Swift 4, 107 bytes

... Yikes.

{a in Dictionary(grouping:a.enumerated()){0ドル.1}.sorted{0ドル.1.first!.0<1ドル.1.first!.0}.map{[0ドル]+1ドル.flatMap{0ドル.0}}}

Ungolfed:

let f = { (input: [Int]) -> [[Int]] in
 return Dictionary(grouping: input.enumerated(), by: { 0ドル.element })
 .sorted { pairA, pairB in // Sort by order of first appearence (lowest offset)
 return pairA.value.first!.offset < pairB.value.first!.offset
 }.map { element, pairs in
 return [element] + pairs.map{ 0ドル.offset /* +1 */} // add 1 here for 1 based indexing
 }
}

It's too bad that dictionary loses ordering, forcing me to waste so many characters on sorting back again. This sort of abuse of implicit closure arguments (0ドル, 1ドル, ...) and implicit tuple members (.0, .1, ...) is uhhhhh not pretty.

Answer 22

Japt, (削除) 14 (削除ここまで) 9 bytes

0-indexed.

â £ð¶X iX

Try it

â £ð¶X iX
â :Deduplicate
 £ :Map each X
 ð : Get 0-based indices of elements in the input
 ¶X : That are equal to X
 iX : Prepend X

Answer 23

PHP 7.4+, 71 bytes

*73 bytes to quote the $_GET key and avoid Warnings.

Snippet: (Demo)

<?foreach($_GET[A]as$k=>$v){$b[$v][0]=$v;$b[$v][]=$k;}print_r([...$b]);

Based on rep, I assume IsmaelMiguel knows the best way to post php code in this community so I am building from his foundation. It is not clear to me if <? is to be included/counted in my snippet. As this is my maiden post, I am happy for anyone to explain if there is any unnecessary syntax. p.s. I also read Tips for golfing in PHP which seems to me like a terrific candidate for migration to Meta.

The improvements made to Ismael's snippet are:

1. Unconditional assignment of the first element in each subarray (value overwriting)
2. Splatpacking instead of array_values() to reindex the output.

Answer 24

Husk, 6 bytes

mS:1円u

Try it online!

Answer 25

J-uby, 56 bytes

~:^%(:& &:[]|:+&:group_by|~:|&(:*&:flatten)|:|&(:+@|:*))

Attempt This Online!

Answer 26

Clean, (削除) 61 (削除ここまで) 60 bytes

import StdEnv,StdLib
$l=removeDup[[e:elemIndices e l]\\e<-l]

Try it online!

Output is 0-indexed

Answer 27

Kotlin, 83 bytes

{it.mapIndexed{i,c->c to i}.groupBy({(a,b)->a},{(a,b)->b}).map{(a,b)->listOf(a)+b}}

Beautified

{
 it.mapIndexed { i, c -> c to i }
 .groupBy({ (a, b) -> a }, { (a, b) -> b })
 .map { (a, b) -> listOf(a) + b }
}

Test

var f: (List<Int>) -> List<List<Int>> =
{it.mapIndexed{i,c->c to i}.groupBy({(a,b)->a},{(a,b)->b}).map{(a,b)->listOf(a)+b}}
data class Test(val input: List<Int>, val output: List<List<Int>>)
val tests = listOf(
 Test(listOf(3, 2, 2, 3), listOf(listOf(3, 0, 3), listOf(2, 1, 2))),
 Test(listOf(17), listOf(listOf(17, 0))),
 Test(listOf(1, 1), listOf(listOf(1, 0, 1))),
 Test(listOf(1, 1, 2), listOf(listOf(1, 0, 1), listOf(2, 2))),
 Test(listOf(1, 2, 3, 4), listOf(listOf(1, 0), listOf(2, 1), listOf(3, 2), listOf(4, 3))),
 Test(listOf(1, 1, 1, 1), listOf(listOf(1, 0, 1, 2, 3)))
)
fun main(args: Array<String>) {
 for (c in tests) {
 val o = f(c.input)
 if (o != c.output) {
 throw AssertionError("${c.input} -> $o != ${c.output}")
 }
 }
}

TIO

TryItOnline

• Pavel: This sollution is a snippet, not a complete function or program. It requires the variable i to be predefined. You can make this valid by converting it to a lambda that takes a parameter i.
• jrtapsell: Reworked to solve issue raised by @Pavel

Answer 28

Perl 5, 63 + 1 (-a) = 64 bytes

map$k{$_}.=$".++$i,@F;say$_.$k{$_}for sort{$k{$a}-$k{$b}}keys%k

Try it online!

Answer 29

Ruby, (削除) 54 (削除ここまで) 52 bytes

->a{a.map{|i|[i]+(0..a.size).select{|j|a[j]==i}}|[]}

This version allows nil (53 bytes):

->a{a.map{|i|[i]+(0...a.size).select{|j|a[j]==i}}|[]}

Try it online!

• Pavel: The challenge specifies the array will only contain positive integers, and there will be at least one element. nil is not a positive integer.
• Asone Tuhid: @Pavel thanks, I checked but missed it somehow

Answer 30

Factor, 56 bytes

[ dup members swap '[ _ dupd indices swap prefix ] map ]

Try it online!