# Group elements by their displacement

Consider the array [5, 6, 8, 3, 9, 4, 2, 1, 7]. If we list how far each number has moved from it's (1-indexed*) index, we have (considering absolute distance):

Array: [5, 6, 8, 3, 9, 4, 2, 1, 7]
Index: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Dists:  4  4  5  1  4  2  5  7  2

We can then group the elements of the array based on their distance away from their indices:

[[3], [4, 7], [5, 6, 9], [8, 2], [1]]

Additionally, we can optionally include empty lists to indicate distances not there (e.g. 0):

[[], [3], [4, 7], [], [5, 6, 9], [8, 2], [], [1], []]

Note that the maximum distance an element can be from its index is len(list) - 1 and the minimum is 0, so the list (including empty lists) will always be the same length or less as the original list.

*: Note that it doesn't matter if we use 1 or 0 indexing

Given a list of n positive integers, group the elements of the list by their absolute distance from their indices. The input is guaranteed to be a permutation of [1, 2, 3, ..., n] and will have a minimum of 3 elements. You may choose to include empty lists in the output, but only if the length of the output is the same length as the input.

The elements of the groups can be separated with any clear, consistent, non-digit separator, and the groups themselves should be separated in the same way, but with a separator that's different from that used to separate the elements of the groups. For example, spaces and newlines, or nested lists.

This is so the shortest code in bytes wins.

## Test cases

[1, 3, 2] -> [[1], [3, 2]]
[3, 2, 4, 1] -> [[2], [4], [3], [1]]
[1, 2, 3, 4] -> [[1, 2, 3, 4]]
[2, 5, 3, 1, 4, 6] -> [[3, 6], [2, 4], [5, 1]]
[2, 1, 3, 6, 5, 7, 4] -> [[3, 5], [2, 1, 7], [6], [4]]
[1, 7, 4, 2, 8, 6, 3, 5] -> [[1, 6], [4], [2], [8, 5], [3], [7]]
[2, 6, 8, 3, 1, 7, 9, 5, 4] -> [[2, 3, 7], [9], [5], [6, 1], [8, 4]]
[5, 6, 8, 3, 9, 4, 2, 1, 7] -> [[3], [4, 7], [5, 6, 9], [8, 2], [1]]
[1, 7, 5, 10, 8, 9, 6, 3, 4, 2] -> [[1], [6], [5], [8, 9], [7, 3, 4], [10], [2]]
[10, 8, 5, 9, 2, 3, 4, 7, 6, 1, 11, 12] -> [[11, 12], [7], [5], [2, 3, 4, 6], [9], [8], [10, 1]]
[3, 5, 10, 11, 6, 7, 12, 14, 8, 2, 9, 13, 1, 4] -> [[6, 7, 8, 13], [3, 9], [5], [12], [14], [10, 11], [2], [4], [1]]
[6, 14, 8, 9, 12, 4, 13, 7, 5, 15, 10, 11, 3, 1, 2] -> [[7, 10, 11], [4], [5], [6, 8, 9, 15], [13], [12], [3], [14], [1, 2]]
[8, 12, 13, 7, 16, 5, 14, 15, 3, 10, 2, 4, 1, 9, 11, 6] -> [[10], [5], [7], [11], [9], [3], [8, 14, 15], [4], [2], [12, 13, 6], [16], [1]]
[14, 5, 10, 1, 2, 4, 13, 9, 7, 12, 8, 11, 3, 15, 16, 6] -> [[9, 11, 15, 16], [4, 7, 12], [5, 1, 2, 8], [13], [10], [3, 6], [14]]
[19, 8, 16, 15, 2, 6, 11, 18, 12, 9, 3, 14, 4, 1, 7, 5, 17, 13, 10] -> [[6, 17], [9], [14], [2, 12], [11], [13], [8], [3, 7], [4, 10], [18], [15, 5], [16, 1], [19]]
[19, 11, 7, 5, 3, 1, 20, 16, 17, 15, 10, 13, 6, 18, 2, 12, 9, 4, 14, 8] -> [[5, 10, 13], [3], [7, 18, 12], [1, 15, 14], [6], [16, 17, 9], [11], [8], [20, 2], [4], [19]]
• Does the order of the result matter?
Dec 22, 2021 at 0:17
• @Adám No, the order of either the overall list, or the orders of the elements in the groups is irrelevant Dec 22, 2021 at 0:18
• "*: Note that it doesn't matter if we use 1 or 0 indexing" not sure about this , or my answer could be 4Bytes Dec 22, 2021 at 18:48
• Can we take the inputs all lowered by 1 and use 0-based indexing? As mentioned by @AZTECCO in the comment above mine, it does save bytes (my 05AB1E answer would go from 5 to 4 bytes as well). Dec 22, 2021 at 23:03
• @KevinCruijssen Yeah, I think that's fair. Feel free to use 0 indexing (and inputs as a permutation of 0 ... n-1) if you like Dec 22, 2021 at 23:06

# J, 10 bytes

</.~]|@-#\

Try it online!

• </.~ Group by...
• ]|@-#\ Absolute value of |@ input minus all length prefixes (ie, 1 2 3... n)

# JavaScript, 151

x=>x.map((y,i)=>[y,Math.abs(y-i-1)]).sort((a,b)=>a[1]-b[1]).reduce((g,z)=>d-z[1]?(d=z[1],[...g,[z[0]]]):[...g.slice(0,-1),[...g.at(-1),z[0]]],[[]],d=0)
• flag this loool Dec 22, 2021 at 0:09
• Yay, you got post id 240000​! Dec 22, 2021 at 0:10

# Jelly, 4 bytes

ạJĠị

A monadic Link that accepts the list of integers and yields a list of lists of integers.

Does not perform the optional empty list insertions.

Try it online!

### How?

Pretty simple for Jelly this one...

ạJĠị - Link: list of integers, A
J   - range of length of A -> [1,2,...,length(A)]
ạ    - A absolute difference that (vectorises)
Ġ  - group indices of that by their values
ị - use those to index back into A
• Very nice, exactly what I had! Dec 22, 2021 at 0:12

# Factor, 52 bytes

[ dup '[ dup _ index 1 + - abs ] collect-by values ]

The collect-by word postdates build 1525, the one TIO uses, so here's a screenshot of running the above code in build 2101's listener:

collect-by is a combinator that collects values in an associative array by a given quotation. The quotation calculates the difference between an element and its index. Then we take only the values from the associative array, discarding the keys.

# Vyxal, 11 bytes

ż-ȧZ⁽tṡfyĠ•

Try it Online!

The pains of not having tons of array focused built-ins

## Explained

ż-ȧZ⁽tṡfyĠ•
ż           # The range [1, len(input)]
-ȧ         # and the absolute difference with the input
Z        # Zip those together
⁽tṡ     # and sort that by tail - this is a work around way to group one list by the results of a function applied to it
fy   # flatten and uninterleave this - this pushes the original list and the absolute differences but sorted
Ġ  # group the indexes on consecutive items
• # and mold the other list to the shape of that.

# R, 32 bytes

function(x)split(x,(x-seq(x))^2)

Try it online!

(51 bytes if we want to include the empty lists for displacements that don't occur:
function(x)Map(function(n)x[abs(x-s)==n],s<-seq(x)), painfully long because of the double "function" keyword, although this could be replaced by "\" in R≥4.1 for 37 bytes)

# JavaScript (ES6), 48 bytes

The output includes empty lists.

a=>a.map((_,i)=>a.filter((v,j)=>(v+=~j)*v==i*i))

Try it online!

# Python 3 + pandas, 48 bytes

lambda s:s.groupby(abs(s-s.index-1)).apply(list)

Input pd.Series[int], output pd.Series[List[int]]. Could be 46 bytes if we use 0-indexed.

TIO didn't have pandas installed (although it installed NumPy). So no TIO link available.

• Wouldn't it be better with agg instead of apply? You could save 2 bytes with: lambda s:s.groupby(abs(s-s.index-1)).agg(list), 46 bytes. Dec 27, 2021 at 1:57

# Husk, 5 bytes

kS≠€¹

Try it online!

k           # group each x in input by
S≠         # difference between x and
€        # index of x in
¹       # input

g a=(\l->map(\k->[fst m|m<-zip a$map(\n->abs$1+n-a!!n)l,snd m==k])l)[0..length a-1]

Try it online!

# Python 2, 111 bytes

o={}
for a,b in[[abs(x+1-y),y]for x,y in enumerate(input())]:o.setdefault(a,[]).append(b)
print[o[p]for p in o]

Try it online!

Not particularly short or clever but it was fun. Unbelievably o.setdefault(a,[]).append(b) is shorter than any way I could find of using a comparison.

# C (gcc), 91 86 84 bytes

j;i;f(a,n)int*a;{for(i=n*n;i--;j||puts(""))abs(a[j=i%n]-j)-i/n||printf("%d ",a[j]);}

Try it online!

Saved 5 bytes thanks to tsh!!!
Saved 2 bytes thanks to ceilingcat!!!

Inputs a pointer to an array of integers and its length (because pointers in C carry no length info).
Outputs the $$\0\$$-indexed numbers (separated by spaces) in displacements groups on separate lines for each possible displacement (so there may be empty lines).

• 86: j;i;f(a,n)int*a;{for(i=n;i--;puts(""))for(j=n;j--;)abs(a[j]-j)-i||printf("%d ",a[j]);}
– tsh
Dec 22, 2021 at 9:06
• @tsh Reversing order is allowed, nice one - thanks! :D Dec 22, 2021 at 10:25
• @ceilingcat Nice one - thanks! :D Dec 22, 2021 at 16:35

# Wolfram Language (Mathematica), 28 bytes

GatherBy[#,i=0;Abs[#-++i]&]&

Try it online!

(\a->[[y|(j,y)<-a,abs(j-y)==i]|(i,_)<-a]).zip[0..]

Try it online! Uses 0-indexing

# BQN, 13 11 bytesSBCS

Saved 2 bytes thanks to Razetime

{𝕩⊔˜|𝕩-↕≠𝕩}

Run online!

Outputs with empty lists (the first group is at the back though)

The best train I could get was ⊢⊔˜(|⊢-↕∘≠) (also 13 11 bytes). Razetime found two even smaller trains: ⊢⊔˜·|⊒˜⊸- and (|⊒˜⊸-)⊸⊔, both 9 bytes!

{𝕩⊔˜|𝕩-↕≠𝕩}
⊔˜        # Group the elements of
𝕩          # the input by
|𝕩-↕≠𝕩  # the displacements
↕≠𝕩  # Indices of the input: range (↕) to length (≠)
𝕩-     # Distance from each element to its corresponding index
|       # Absolute value

# Charcoal, 11 bytes

ＩＥθΦθ⁼κ↔⁻λμ

Try it online! Link is to verbose version of code. 0-indexed. Output includes empty lists. Lists are double-spaced from each other. Explanation:

θ         Input array
Ｅ          Map over elements
θ       Input array
Φ        Filtered where
λ  Inner value
μ Inner index
↔⁻   Absolute difference
⁼      Equal to
κ     Outer index
Ｉ           Cast to string
Implicitly print

# Python3, 96 bytes:

f=lambda x,i=1,d={}:f(x[1:],i+1,{**d,(j:=abs(x[0]-i)):d.get(j,[])+[x[0]]})if x else[*d.values()]

Try it online!

# Ruby, 42 bytes

->a{r=0;a.group_by{|x|(x-r+=1)**8}.values}

Try it online!

# 05AB1E, 4 bytes

.¡Nα

Input and index-comparison are both 0-based.

The groups are sorted based on their first occurrence, rather than their index-difference, which is allowed in the comments. If this wouldn't have been the case, it would be this 14 bytes monstrosity instead (with 1-based input/comparison), since 05AB1E lacks a sort + group-by builtin in one, and doing them one at a time when comparing it to their index isn't exactly ideal..

āøΣÆÄ}.¡ÆÄ}€€н

Explanation:

.¡       # Group the (implicit) input-list by:
N      #  Push the 0-based index
α     #  Get the absolute difference of this index and the number
# (after which the list of lists is output implicitly as result)

ā        # Push a list in the range [1,input-length]
ø       # Create pairs with the input-list
Σ      # Sort this list of pairs by:
Æ     #  Reduce the pair by subtracting
Ä    #  And take the absolute value of that
}.¡ÆÄ  # After the sort-by, do the same with a group-by
}€   # After the group-by, map over each list of pairs:
€  #  Map over each inner pair:
н #   Only leave the first value
# (after which the list of lists is output implicitly as result)

# Japt-Q, 4 bytes

üÈaY

Try it

• saved 1 by 0-indexing
ü      - sort and group by:
È     - f(value,index)
aY   - distance(value,index)

# Python 2, 70 bytes

l=input()
d=[[]for _ in l]
n=1
for x in l:d[abs(x-n)]+=x,;n+=1
print d

Try it online!

Full program. Output includes empty lists.

-11 thanks to @loopywalt

• eval... can be [[]for _ in l] (-11); +=[x] can be +=x, (-1) Dec 22, 2021 at 11:47
• @loopywalt thanks!!! Dec 23, 2021 at 5:59
• I think []*len(l) does the same as [[]for _ in l] and it’s 5 bytes shorter… Dec 26, 2021 at 9:33
• @agtoever no it dosen't work, to know why see this Stack Overflow question Dec 26, 2021 at 9:46
• Ah. Yes. You’re right. Dec 26, 2021 at 10:07

# Python/NumPy, 47 bytes (@tsh)

lambda a:[[*a[abs(a-sorted(a))==i]]for i in~-a]

Attempt This Online!

#### Python/NumPy, 49 bytes

lambda a:[[*a[(a-sorted(a))**2==i*i]]for i in~-a]

Attempt This Online!

Avoiding explicit numpy import saves 15.

#### Python/NumPy, 64 bytes

lambda a:[[*a[abs(a-sort(a))==i]]for i in~-a]
from numpy import*

Attempt This Online!

This version exploits that OP doesn't care for order.

#### Python/NumPy, 71 bytes

lambda a:[[*a[abs(a-sort(a))==i]]for i in sort(a)-1]
from numpy import*

Attempt This Online!

Expects a numpy array but outputs a plain list of lists instead of a list of arrays which would be 3 bytes shorter but looks rather ugly.

• lambda a:[[*a[abs(a-sorted(a))==i]]for i in~-a]
– tsh
Dec 22, 2021 at 6:57
• And I believe lambda a:[a[abs(a-sorted(a))==i]for i in~-a] is also valid.
– tsh
Dec 22, 2021 at 6:59

# Scala 3, 64 bytes

l=>l.indices.map(d=>l.indices.filter(i=>(i+1-l(i)).abs==d)map l)

Attempt This Online!

Includes empty lists.

f x=[[b|(a,b)<-zip[0..]x,abs(a-b)==y]|y<-x]

Try it online!

Zero indexing. Outputs with empty lists.

Nothing really clever here. I'm quite surprised that this is the shortest of 3 Haskell answers.

## Explanation

We have a first list comprehension

f x=[...|y<-x]

From x it takes all the possible distances we are looking for. Since x is a permutation every number we want appears and it appears exactly once.

Inside we have a second comprehension.

f x=[[...|(a,b)<-zip[0..]x,...]|y<-x]

Here we take an index and a value from x. Using zip to get the indexes.

f x=[[...|(a,b)<-zip[0..]x,abs(a-b)==y]|y<-x]

We filter only the ones such that their absolute difference is the desired distance.

f x=[[b|(a,b)<-zip[0..]x,abs(a-b)==y]|y<-x]

Then we return the value.

0 indexed

# Haskell + hgl, 21 bytes

1 indexed

## Explanation

The main crux of this is bgB which groups a list into chunks using a conversion function. This function was inspired by this answer.

The first thing we do in each answer is pair every element with it's index. For zero indexed that's eu, but for one indexed it's a little more expensive zp nN.

Then we do the grouping. We use bgB and our conversion function is the absolute difference aD. Since we need to operate on a tuple we have to uncurry aD with Uc.

Once we've made the groups we need to go remove the indexes, cr gets the second element of a tuple so we triple map cr to get the second element of every tuple.

## Reflection

This feels very big for what it's doing. It's nice we have the bgB to work with, but it doesn't quite fit here. The issue is that bgB is a very local function but index is a non-local property. So we need to put the indexes in, and then take them out. Not to mention this adds the currying necessary.

It's possible to imagine a version of bgB that doesn't have this issue, but it seems like it would be very specific to this problem.