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

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']
];

Answer 1

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)

Answer 2

Решение на TypeScript:

const permutate = <T>(arr: T[], k: number, withRepetition = false) => {
  const permutations: T[][] = []
  const permutation: T[] = Array(k)
  const internalPermutate = (elements: T[], depth: number): void => {
    if (depth === k) {
      permutations.push([...permutation])
      return
    }
    elements.forEach((element, index) => {
      permutation[depth] = element
      // Условное удаление элемента из массива по индексу
      const partial = withRepetition
        ? elements
        : [...elements.slice(0, index), ...elements.slice(index + 1)]
      internalPermutate(partial, depth + 1)
    })
  }
  internalPermutate(arr, 0)
  return permutations
}

Решение на JavaScript:

const permutate = (arr, k, withRepetition = false) => {
  const permutations = []
  const permutation = Array(k)
  const internalPermutate = (elements, depth) => {
    if (depth === k) {
      permutations.push([...permutation])
      return
    }
    elements.forEach((element, index) => {
      permutation[depth] = element
      const partial = withRepetition
        ? elements
        : [...elements.slice(0, index), ...elements.slice(index + 1)]
      internalPermutate(partial, depth + 1)
    })
  }
  internalPermutate(arr, 0)
  return permutations
}


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

const permutations = permutate(array, k)
console.log({ permutations : permutations.map(p => p.join()) })

Примечание: решение на основе автоподсказок GitHub Copilot.

БЛОГ НА HUSL

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

Ответы (2 шт):