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.

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

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

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

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.

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

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

Ṗ'ż-ȧ⁰≤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?

```