Shuffle an array, a little bit

Question

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.

• chunes: Is the input a possible output or do we have to force each element to change?
• flawr: @chunes The input is a possible output: All permissible permutations must be able to occur!
• naffetS: We can't guarantee that the input has no duplicates, correct?
• flawr: @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.
• flawr: @Steffan Yes the input may contain duplicates.

Answer 1

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.

Answer 2

05AB1E, (削除) 9 (削除ここまで) (削除) 7 (削除ここまで) 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)

Answer 3

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
 ], //
 b = [] // start with b[] = empty array
) ? // end of every; if sucessful:
 b // return b[]
: // else:
 g(k) // try again

Answer 4

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:
 ʋ - last four links as a dyad - f(P, k+1):
 { - use k+1 with:
 J - range of length -> I = [1..k+1]
 ạ - P absolute difference I (vectorises) -> distances
 Ṁ - maximum
 < - is less than k+1?

Answer 5

Ruby, (削除) 72 (削除ここまで) (削除) 64 (削除ここまで) (削除) 63 (削除ここまで) 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

Answer 6

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.

Answer 7

Vyxal r, (削除) 17 (削除ここまで) (削除) 13 (削除ここまで) 11 bytes

ʁṖ'→ƛ←ḟε;G≥

Try it Online!

-4 bytes thanks to emanresu A

-1 byte thanks to Aaroneous Miller

• emanresu A: Nice! The Both : are unnecessary, and you can use the nameless variable for -2 bytes. (Or the register)
• emanresu A: 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.
• naffetS: Thanks, I knew about both, actually.
• Aaroneous Miller: You can use the r flag for -1 byte (Also you need to use ≥ or ≤ at the end instead of > or <)
• naffetS: < was fine because I was taking k+1, but I guess k works fine.

Answer 8

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!

Answer 9

Charcoal, 29 bytes

NθFN⊞υ0W⊙υ∨⊖Noυλ‹θ↔−κλUMυ‽LυIυ

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

Nθ

Input k.

FN⊞υ0

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

W⊙υ∨⊖Noυλ‹θ↔−κλ

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

UMυ‽Lυ

... randomise the permutation.

Iυ

Output the permissible permutation.

Answer 10

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

• naffetS: -5 bytes...
• Tipping Octopus: k>Z[n]-n>-k for n in L for -7 bytes if you switch to 0-indexing for L

Answer 11

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

Answer 12

Haskell (Lambdabot), 72 bytes

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!

Answer 13

Vyxal, 8 bytes

Ṗ'ż-ȧ0≤A

Try it Online!

Port of 05AB1E.

How?

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

```