How to implement the generation of placements without repetitions?

Question

How to implement the generation of placements without repetitions?

How best to implement the permutate function with the signature (JavaScript)

const array = ['a', 'b', 'c'];
const k = 2;

const permutations = permutate(array, k);

Where permutations is everything placements from array to k (all possible k - element ordered subsets without repetitions from array)?

Example of expected return value:

const permutations = [
    ['a', 'b'], ['b', 'a'], ['b', 'c'], ['c', 'b'], ['a', 'c'], ['c', 'a']
];

1

алгоритм математика любой-язык дискретная-математика комбинаторика

Author: Артём Ионаш, 2020-11-16

Source

1 answers

score 4 · Answer 1

Delphi (does not require transmitting the current state):

procedure Arrangement(var A: array of Integer; n, k: Integer; s: string);
  var
    i, t: Integer;
  begin
    if k = 0 then
      Output(s)
    else
      for i := 0 to n - 1 do begin
        t := A[i];
        A[i] := A[n - 1];  //store used item in the tail
        Arrangement(A, n - 1, k - 1, s + IntToStr(t) + ' ');  //recursion without tail
        A[i] := t;  //get it back
      end;
  end;

C++ (153 corresponds to 1,5,3)

void GenArrangement(int n, int k, int idx, int used, int arran) {
    if (idx == k) {
        std::cout << arran << std::endl;
        return;
    }

    for (int i = 0; i < n; i++) 
        if (0 == (used & (1 << i))) 
            GenArrangement(n, k, idx + 1, used | (1 << i), arran * 10 + (i + 1));
}

int main()
{
    GenArrangement(5, 3, 0, 0, 0);
}

Python

def genArr(n, k, ar, used, idx):
    for i in range(n):
        if not i in used:
            used.add(i)
            ar[idx] = i
            if idx == k - 1:
                print(ar) #comment for large n
            else:
                genArr(n, k, ar, used, idx + 1)
            used.remove(i)

n = 5
k = 3
genArr(n, k, [0]*k, set(), 0)