Все возможные комбинации одномерного массива

#комбинаторика

Друзья подскажите в теории, какие бывают практики к подходу вычисления количества
возможных комбинаций из элементов одномерного массива. И перебрать все возможные последовательности.
Например есть элементы 2,45,16,34 - как узнать возможные комбинации? ( не прошу кода,
прошу теорию)    

Ответы

Ответ 1

Перестановки

Перестановки - это комбинации изначального массива, получаемые перестановкой элементов.
Количество перестановок An = n! Алгоритм получения перестановки по номеру (1..n!) таков:



var facts = [];
function fact(N){
    if(N==0 || N==1) return 1;
    if(facts[N]) return facts[N];
    facts[N] = N*fact(N-1);
    return facts[N];
}
function permutation(index, A){
    var n=A.length;
    var i=index+1;
    var res=[];
    for(var t=1;t<=n;t++){
        var f = fact(n-t);
        var k=Math.floor((i+f-1)/f);
        res.push(A.splice(k-1,1)[0]);
        i-=(k-1)*f;
    }
    if (A.length) res.push(A[0]);
    return res;
}

function log(){
  var msg = Array.prototype.slice.call(arguments).join(" ");
  document.getElementById("log").value+="\n"+msg;
  console.log(arguments);
}
var M = ["A","B","C","D","E"];
for(var i=0;i




Смысл заключается в том, что мы на каждой итерации берем элемент из массива и убираем
его, переходя к следующей итерации, имеем массив меньшей длины... и так продолжаем
пока исходный массив не опустеет. При этом номер комбинации получается исходя из порядка
вынимания элементов массива. Аналогичный подход используется в алгоритме Фишера–Йетса
для перемешивания массива, только там элемент, который будет выбран на каждой итерации
берется случайным образом.

Сочетания

Сочетания - это наборы определенной длины (k), составленные из множества определенной
длины (n). Сочетания, в которых одни те же элементы поменены местами, считаются одним
сочетанием, поэтому для удобства берутся те сочетания, элементы в которых упорядочены
по возрастанию (в лексикографическом порядке). Количество сочетаний C(n,k) - читается
как "Це из эн по ка", = n!/(k!(n-k)!), называются биномиальными коэффициентами. Алгоритм
получения сочетания по номеру таков:



var facts = [];

function fact(N) {
  if (N == 0 || N == 1) return 1;
  if (facts[N]) return facts[N];
  facts[N] = N * fact(N - 1);
  return facts[N];
}

function C(n, k) {
  return fact(n) / fact(k) / fact(n - k);
}

function combination(index, k, A) {
  var res = [0];
  var n = A.length;
  var s = 0;
  for (var t = 1; t <= k; t++) {
    var j = res[t - 1] + 1;
    while ((j < (n - k + t)) && ((s + C(n - j, k - t)) <= index)) {
      s += C(n - j, k - t);
      j++;
    }
    res.push(j);
  }
  res.splice(0, 1);
  return res;
}

function log() {
  var msg = Array.prototype.slice.call(arguments).join(" ");
  document.getElementById("log").value += "\n" + msg;
  console.log(arguments);
}
var M = ["A", "B", "C", "D", "E"];
for (var i = 0; i < C(M.length, 3); i++) {
  log(i, combination(i, 3, M.slice(0)).join(""));
}
html,
body {
  margin: 0;
  padding: 0;
  height: 100%
}
#log {
  width: 100%;
  height: 100%;
  border: 0;
  padding: 0;
  display: block
}





Номер сочетания берется как сумма всех биномиальных коэффициентов для массивов уменьшающейся
длины (на самом деле сформулировать кратко и притом понятно принцип нумерации сложно,
ссылка на теорию будет ниже).

Размещения

Сочетания и перестановки являются частными случаями размещений. 
Размещения - это сочетания, где важен порядок элементов. Или, другими словами, это
перестановки сочетаний. Количество размещений A(n,k)=k!*C(n,k)=n!/(n-k)!.
Таким образом, чтоб получить размещение по номеру, делим общее количество размещений
на цело на номер - получаем номер сочетания, и применяем к нему перестановку с номером
как остаток от деления количества размещений на номер размещения.

Размещения с повторениями

Отдельным вариантом комбинации является размещение с повторением. A'(n,k) = n^k.
Т.е. все варианты массивов длины k, где на каждой позиции может быть любой элемент
из множества размера n. Самый простой для понимания вариант - это A(10,k) -  все десятичные
числа от 0 до 10^k-1. Или A(2,k) - все двоичные числа длины k.
Нумерация элементов натуральная, индекс комбинации соответствует десятичному аналогу
числа в n-ричной системе счисления.

См. также

Про нумерацию размещений и сочетаний можно почитать в статье "О нумерации перестановок
и сочетаний для организации параллельных вычислений в задачах проектирования управляющих
систем" (гуглится), алгоритмы приведены оттуда, ссылки в статье ведут на:


Дейкстра Э. Дисциплина программирования.
Липский В. Комбинаторика для программистов.


Оптимизация

Поскольку расчеты ведутся с использованием факториалов, то для больших значений n,k
скорее всего может потребоваться длинная арифметика. В то же время вполне возможно,
что точное вычисление факториала не понадобится (надо проверять), и достаточно будет
формулы Стирлинга... В приведенных алгоритмах функция факториала написана для простоты
понимания.

Обратная задача

Каждый из вариантов комбинаций может иметь обратную задачу - получение номера по
комбинации. Имея представление о принципе нумерации обратная задача также решается.
Например, для размещений с повторениями - это перевод n-ричной системы счисления в
десятичную...

Использование

Имея рассчитанные значения факториалов или вообще таблиц со всеми комбинациями определенного
типа есть возможность получения случайной комбинации с использованием только одного
вызова ГСЧ для получения комбинации.


Ответ 2

Не знаю, как это делается на php, но в теории можно применить следующий алгоритм:

Перебираем все числа от 0 (ни одного элемента) до (2^n) - 1 (все элементы), где n
- длина масcива.

На каждом шаге перебора смотрим все биты числа, и если i-й бит равен единице, то
i-й элемент будет входить в комбинацию.

Например, для трёх элементов:


0 - нет элементов
1 - (001) только 1й элемент
2 - (010) только 2й
3 - (011) 2й и 1й
4 - (100) только 3й
5 - (101) 1й и 3й
6 - (110) 1й и 2й
7 - (111) 1й, 2й, 3й


Ответ 3

var facts = [];
function fact(N){
    if(N==0 || N==1) return 1;
    if(facts[N]) return facts[N];
    facts[N] = N*fact(N-1);
    return facts[N];
}
function permutation(index, A){
    var n=A.length;
    var i=index+1;
    var res=[];
    for(var t=1;t<=n;t++){
        var f = fact(n-t);
        var k=Math.floor((i+f-1)/f);
        res.push(A.splice(k-1,1)[0]);
        i-=(k-1)*f;
    }
    if (A.length) res.push(A[0]);
    return res;
}

function log(){
  var msg = Array.prototype.slice.call(arguments).join(" ");
  document.getElementById("log").value+="\n"+msg;
  console.log(arguments);
}
var M = ["п","о","б","а","е","с","п","р","о","с","и","у"];
for(var i=0;i