Group elements by their displacement

Question

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

Answer 1

J, 10 bytes

</.~]|@-#\

Try it online!

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

Answer 2

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

Answer 3

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)

Answer 4

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.

Answer 5

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.

Answer 6

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)

Answer 7

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.

Answer 8

05AB1E, 4 bytes

.¡Nα

Input and index-comparison are both 0-based.

Try it online or verify all test cases.

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

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

Try it online or verify all test cases.

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)

Answer 9

Wolfram Language (Mathematica), 28 bytes

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

Try it online!

Answer 10

Japt -Q, 4 bytes

üÈaY

Try it

• saved 1 by 0-indexing

ü      - sort and group by:
 È     - f(value,index)
  aY   - distance(value,index) 

Answer 11

BQN, 13 11 bytes^SBCS

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

Answer 12

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!

Answer 13

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.

Answer 14

Ruby, 42 bytes

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

Try it online!

Answer 15

Husk, 5 bytes

kS≠€¹

Try it online!

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

Answer 16

Haskell, 83 bytes

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!

Answer 17

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

Answer 18

Haskell, 50 bytes

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

Try it online! Uses 0-indexing

Answer 19

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

Answer 20

Haskell, 43 bytes

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.

Answer 21

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

Answer 22

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!

Answer 23

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.

Answer 24

Haskell + hgl, 18 bytes

cr<<<bgB(Uc aD)<eu

0 indexed

Haskell + hgl, 21 bytes

cr<<<bgB(Uc aD)<zp nN

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.

Answer 25

APL(Dyalog Unicode), 24 bytes ^SBCS

{⍵∘{⍺[⍸⍵=1+|⍺-⍳≢⍺]}¨⍳≢⍵}

Outputs with empty lists.

Try it on APLgolf!

Idk how to convert this to tacit lol, I'm sure it's possible though.

{⍵∘{⍺[⍸⍵=1+|⍺-⍳≢⍺]}¨⍳≢⍵}
{                      }             ⍝  a dfn in which...
                   ¨                 ⍝  for each element in...
                    ⍳≢⍵              ⍝  the range 1 to the length of the input...
 ⍵∘{⍺[⍸⍵=1+|⍺-⍳≢⍺]}                  ⍝  apply the following function, 
                                         with original the input passed in as the left argument:
   {     1+|⍺-⍳≢⍺ }                  ⍝  calculate the distance between the original list
                                         and its indices + 1...
      ⍸⍵=                            ⍝  and keep the ones that are equal to the right argument
                                         (which is an element from the range we are looping over)
    ⍺[           ]                   ⍝  then index the input (left argument)
                                         with the filtered list of indices

Answer 26

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.

Answer 27

Arturo, 34 bytes

$=>[0gather&=>[abs&-dup+1]|values]

Try it