20
\$\begingroup\$

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.
\$\endgroup\$
12
  • 1
    \$\begingroup\$ Is the input a possible output or do we have to force each element to change? \$\endgroup\$
    – chunes
    Apr 4 at 19:31
  • \$\begingroup\$ @chunes The input is a possible output: All permissible permutations must be able to occur! \$\endgroup\$
    – flawr
    Apr 4 at 19:35
  • 2
    \$\begingroup\$ We can't guarantee that the input has no duplicates, correct? \$\endgroup\$
    – Steffan
    Apr 4 at 22:19
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – flawr
    Apr 5 at 7:09
  • 1
    \$\begingroup\$ @Steffan Yes the input may contain duplicates. \$\endgroup\$
    – flawr
    Apr 5 at 7:12

13 Answers 13

6
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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?
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
0
2
\$\begingroup\$

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.
\$\endgroup\$
2
+100
\$\begingroup\$

Vyxal r, 17 13 11 bytes

ʁṖ'→ƛ←ḟε;G≥

Try it Online!

-4 bytes thanks to emanresu A

-1 byte thanks to Aaroneous Miller

\$\endgroup\$
5
  • \$\begingroup\$ Nice! The Both : are unnecessary, and you can use the nameless variable for -2 bytes. (Or the register) \$\endgroup\$
    – emanresu A
    Apr 8 at 21:34
  • \$\begingroup\$ 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. \$\endgroup\$
    – emanresu A
    Apr 9 at 1:22
  • \$\begingroup\$ Thanks, I knew about both, actually. \$\endgroup\$
    – Steffan
    Apr 9 at 1:25
  • \$\begingroup\$ You can use the r flag for -1 byte (Also you need to use or at the end instead of > or <) \$\endgroup\$ Apr 14 at 0:50
  • \$\begingroup\$ < was fine because I was taking k+1, but I guess k works fine. \$\endgroup\$
    – Steffan
    Apr 14 at 17:26
1
\$\begingroup\$

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!

\$\endgroup\$
0
1
\$\begingroup\$

Charcoal, 29 bytes

NθFN⊞υ⁰W⊙υ∨⊖№υλ‹θ↔⁻κλUMυ‽LυIυ

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

Nθ

Input k.

FN⊞υ⁰

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

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

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

UMυ‽Lυ

... randomise the permutation.

Iυ

Output the permissible permutation.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ -5 bytes... \$\endgroup\$
    – Steffan
    Apr 5 at 2:54
  • \$\begingroup\$ k>Z[n]-n>-k for n in L for -7 bytes if you switch to 0-indexing for L \$\endgroup\$ Apr 5 at 5:50
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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?

```

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.