# Shuffle an array, a little bit

Given some input array a = [a1, a2, ..., an] and a positive integer k, shuffle the input array a such that no entry is farther than k from its initial position.

### Example

Given the array [1, 2, 3, 4, 5, 6] and k = 1, this means the entry 3 can be at following positions:

[*, 3, *, *, * ,*]
[*, *, 3, *, *, *]   (original position)
[*, *, *, 3, *, *]


### Details

• Uniform randomness over all permissible permutations is not required, but
• You can assume the input array is limited to the range [1, n] (or [0, n-1], where n is the length).
• all permissible permutations must have a nonzero probability of occurring.
• Instead of shuffling an input array, you can also just take k and the length of the array n (or n+-1 alternatively) as an input, and output a permutation in a suitable encoding (i.e as a list of indices etc). For this you can use 0 or 1 based indexing.
• Instead of k you can also take k-1 or k+1 as an input if it is more suitable.
• You can assume that 0 < k < [length of array].
• Alternatively to sampling one random permutation you can also output all permissible permutations.
• Is the input a possible output or do we have to force each element to change? Apr 4, 2022 at 19:31
• @chunes The input is a possible output: All permissible permutations must be able to occur! Apr 4, 2022 at 19:35
• We can't guarantee that the input has no duplicates, correct? Apr 4, 2022 at 22:19
• @KevinCruijssen Under the current rules yes it can be arbitrary, but I think we can add this assumption as it leads to no loss of generality. Apr 5, 2022 at 7:09
• @Steffan Yes the input may contain duplicates. Apr 5, 2022 at 7:12

# R, 47 bytes

\(n,k){while(any(abs((a=sample(n))-1:n)>k))0
a}

Attempt This Online!

Takes the length n and the maximum distance allowed k and returns a permutation on 1:n by rejection sampling.

Footer computes 10000 iterations of f(6,1) and tabulates the results for each index to give a rough distribution.

# 05AB1E, 97 6 bytes

œʒāα@P


1-based input-list, and outputs all possible permutations. Outputting a random one would be 2 bytes longer by adding a trailing }Ω.

Try it online.

Explanation:

œ       # Push a list of permutations of the first (implicit) input-list
ʒ      # Filter this list of permutations by:
ā     #  Push a list in the range [1,length] (without popping)
α    #  Get the absolute difference between the values at the same positions
@   #  Check for each whether the second (implicit) input is >= the value
P  #  Product to check if all are truthy
# (after which the filtered list is output implicitly)


# JavaScript (ES6),  89  87 bytes

Expects (array)(k).

a=>g=k=>a.every((v,i)=>!(1/b[j=i+Math.random()*(k-~k)-k|0])/a[j]&&[b[j]=v],b=[])?b:g(k)


Try it online!

### Commented

a =>                   // a[] = input array
g = k =>               // k = max. distance
a.every((v, i) =>      // for each value v at position i in a[]:
!(                   //   abort if:
1 / b[             //     - b[j] is already defined
j = i +          //       where j is randomly chosen in
Math.random() *  //       [i-k .. i+k]
(k - ~k) - k | 0 //
]                  //   or:
) / a[j] &&          //     - a[j] is not defined
[                    //   otherwise:
b[j] = v           //     set b[j] to v and keep going
],                   //
) ?                    // end of every; if sucessful:
b                    //   return b[]
:                      // else:
g(k)                 //   try again


# Jelly, 9 bytes

Œ!ạJ{Ṁ<ʋƇ


A dyadic Link that accepts the length, n, on the left and the minimum illegal distance, k+1, on the right and yields a list of all permutations as 1-indexed indices.

Try it online!

### How?

Œ!ạJ{Ṁ<ʋƇ - Link: n; k+1
Œ!        - all permutations of [1..n]
Ƈ - filter keep those for which:
{     -     use k+1 with:
J      -       range of length -> I = [1..k+1]
ạ       -     P absolute difference I (vectorises) -> distances
Ṁ    -     maximum
<   -     is less than k+1?


# Ruby, 726463 62 bytes

Lambda that accepts length of array minus one n-1, and minimum illegal distance for an element to be moved k+1.

->n,k{a=*0..n;a.shuffle!.all?{(a.index(_1)-_1).abs<k}||redo;a}


Attempt This Online!

-8 bytes thanks to @Dingus

# Python 3, 104 94 92 bytes

## Code

lambda l,k:[p for p in permutations(l)if all(-k<p[i]-i<k for i in l)]
from itertools import*


Takes as input:

• The list [0, 1, ..., n-2, n-1] where n is the length of the list
• k+1

Outputs all possible permutations.

Try it online!

## Explanation

• Uses itertools.permutations to get all permutations of the list.
• Only adds each one to the output list if -k<p[i]-i<k is True for every index i and value p[i] in the permutation.

# Vyxalr, 1713 11 bytes

ʁṖ'→ƛ←ḟε;G≥


Try it Online!

-4 bytes thanks to emanresu A

-1 byte thanks to Aaroneous Miller

• Nice! The Both : are unnecessary, and you can use the nameless variable for -2 bytes. (Or the register) Apr 8, 2022 at 21:34
• FYI, there's a Vyxal chat if you need help with anything, and there's a deadlineless bounty for five Vyxal answers if you want that. Apr 9, 2022 at 1:22
• Thanks, I knew about both, actually. Apr 9, 2022 at 1:25
• You can use the r flag for -1 byte (Also you need to use ≥ or ≤ at the end instead of > or <) Apr 14, 2022 at 0:50
• < was fine because I was taking k+1, but I guess k works fine. Apr 14, 2022 at 17:26

# Python3, 178 bytes:

lambda a,k:f([*enumerate(a)],k,a,0,[])
def f(a,k,l,j,c):
if len(a)==j:yield c;return
for x,y in a:
if abs(x-j)<=k and(C:=list.count)(l,y)>C(c,y):yield from f(a,k,l,j+1,c+[y])


Try it online!

# Charcoal, 29 bytes

ＮθＦＮ⊞υ⁰Ｗ⊙υ∨⊖№υλ‹θ↔⁻κλＵＭυ‽ＬυＩυ


Try it online! Link is to verbose version of code. Outputs a random permissible permutation. Explanation:

Ｎθ


Input k.

ＦＮ⊞υ⁰


Input n and create an illegal permutation (unless n=1, in which case there is only one permutation).

Ｗ⊙υ∨⊖№υλ‹θ↔⁻κλ


Repeat until the permutation is both legal and permissible...

ＵＭυ‽Ｌυ


... randomise the permutation.

Ｉυ


Output the permissible permutation.

# Python, 106 bytes

from random import*
f=lambda L,k:(shuffle(Z:=L[::])or all([k>abs(s-n)for n,s in zip(L,Z)])and Z or f(L,k))

Attempt This Online!

Returns a new list. Requires the input list to be in the format [1,2,...,n-1,n] where n is the length of the list. Taking k+1 as an input

• -5 bytes... Apr 5, 2022 at 2:54
• k>Z[n]-n>-k for n in L for -7 bytes if you switch to 0-indexing for L Apr 5, 2022 at 5:50

# Factor + math.combinatorics math.unicode, 66 bytes

[ iota dup [ v- vabs [ >= ] with ∀ ] 2with filter-permutations ]


Try it online!

Takes $$\k\$$ and a length $$\l\$$ and outputs all zero-indexed sets of indices of length $$\l\$$ that satisfy the distance constraint given by $$\k\$$.

Operator # that accepts length of array minus one n-1, and minimum illegal distance for an element to be moved k+1.

n#k=[x|x<-permutations[0..n],all(\y->abs(fromJust(elemIndex y x)-y)<k)x]

Attempt This Online!

# Vyxal, 8 bytes

Ṗ'ż-ȧ⁰≤A


Try it Online!

Port of 05AB1E.

## How?

Ṗ'ż-ȧ⁰≤A
Ṗ        # All permutations of the (implicit) first input
'       # Filter by:
ż      #  Length range [1, length]
-ȧ    #  Absolute differences of values in the same positions
⁰≤  #  For each, is it less than or equal to the second input?
A #  Are they all truth?


$$`$$