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!

Answer 1

Dyalog APL, 5 bytes

(⊂,)⌸

Try it online!

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

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

Answer 3

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 4

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!

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

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

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

Answer 10

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 11

Wolfram Language (Mathematica), 40 bytes

Saved a byte thanks to Martin Ender.

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

Try it online!

Answer 12

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!

Answer 13

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

Answer 14

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 15

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
└∊───────────┘

Answer 16

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 17

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 18

Julia 0.6, 37 bytes

Thanks to Pavel for 1 byte off.

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

Try it online!

Answer 19

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]]

Answer 20

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 21

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 22

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 23

Clean, 61 60 bytes

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

Try it online!

Output is 0-indexed

Answer 24

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!

Answer 25

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

Answer 26

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 27

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

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

Try it online!