Как реализовать генерацию размещений без повторений?

Question

Как лучше реализовать функцию permutate с сигнатурой (JavaScript)
const array = ['a', 'b', 'c'];
const k = 2;

const permutations = permutate(array, k);

где permutations — все размещения из array по k (все возможные k-элементные упорядоченные подмножества без повторений из array)?

Пример ожидаемого возвращённого значения:
const permutations = [
    ['a', 'b'], ['b', 'a'], ['b', 'c'], ['c', 'b'], ['a', 'c'], ['c', 'a']
];

MBo · Answer

Delphi (не требует передачи текущего состояния):
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 соответствует 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)

Как реализовать генерацию размещений без повторений?

One Answer

Add your own answers!

Ask a Question