Все возможные комбинации одномерного массива
1,00
р.
Друзья подскажите в теории, какие бывают практики к подходу вычисления количества возможных комбинаций из элементов одномерного массива. И перебрать все возможные последовательности.
Например есть элементы 2,45,16,34 - как узнать возможные комбинации? ( не прошу кода, прошу теорию)
Ответ
Перестановки
Перестановки - это комбинации изначального массива, получаемые перестановкой элементов. Количество перестановок 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+="<br>"+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 += "<br>" + 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,45,16,34 - как узнать возможные комбинации? ( не прошу кода, прошу теорию)
Ответ
Перестановки
Перестановки - это комбинации изначального массива, получаемые перестановкой элементов. Количество перестановок 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+="<br>"+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 += "<br>" + 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-ричной системы счисления в десятичную...
Использование
Имея рассчитанные значения факториалов или вообще таблиц со всеми комбинациями определенного типа есть возможность получения случайной комбинации с использованием только одного вызова ГСЧ для получения комбинации.
