Сочетания, размещения, сочетания с повторениями, размещения с повторениями.

n = k =
Не использовать медленный алгоритм нахождения сочетаний, размещений и сочетаний с повторениями.

Число сочетаний, размещений, сочетаний с повторениями, размещений с повторениями.

n =
k =

Алгоритм нахождения всех размещений с повторениями из n по k.

Изначально массив y представляет собой массив из k единиц. Затем в цикле, начиная с последнего элемента массива, пока значение этого элемента равно n, двигаемся от конца массива к началу, пока не встретим элемент, который меньше n. Затем увеличиваем этот элемент, меньший n, на единицу, а все элементы, стоящие после него до конца массива приравниваем единице. Выходом из цикла является условие: все элементы массива y равны n.

Каждый массив y, начиная с массива из k элементов, равных 1, и кончая массивом из k элементов, равных n, переписывается в очередное значение двумерного массива x, содержащего все размещения с повторениями из n элементов по k, число которых равно nk.

Алгоритм нахождения всех размещений с повторениями  из n элементов по k элементов

Алгоритм нахождения всех сочетаний с повторениями из n по k.

Изначально массив y представляет собой массив из k единиц. Затем в цикле, начиная с последнего элемента массива, пока значение этого элемента равно n, двигаемся от конца массива к началу, пока не встретим элемент, который меньше n. Затем увеличиваем этот элемент, меньший n, на единицу, а все элементы, стоящие после него до конца массива приравниваем этому предшествующему элементу.Выходом из цикла является условие: все элементы массива y равны n.

Каждый массив y, начиная с массива из k элементов, равных 1, и кончая массивом из k элементов, равных n, переписывается в очередное значение двумерного массива x, содержащего все размещения с повторениями из n элементов по k, число которых равно nk.

Алгоритм нахождения всех сочетаний с повторениями  из n элементов по k элементов

Алгоритм нахождения всех сочетаний из n по k.

Изначально массив y представляет собой массив из k подряд идущих натуральных чисел от 1 до k. Затем в цикле, начиная с последнего элемента массива, отстоящего от конца массива на расстоянии p = 0, пока значение этого элемента, отстоящего от конца массива на расстоянии p, равно n - p, двигаемся от конца массива к началу, увеличивая значение p на единицу, пока не встретим элемент, который меньше n - p. Затем увеличиваем этот элемент, меньший n - p, на единицу, а все элементы, стоящие после него до конца массива, являются частью строго возрастающей арифметической прогрессии со знаменателем 1, то есть последовательностью подряд идущих друг за другом натуральных чисел. Выходом из цикла является условие: все элементы массива y представляют собой часть строго возрастающей арифметической прогрессией со знаменателем 1 длины k с начальным членом n - k + 1 и конечным членом n.

Каждый массив y, начиная с массива из k первых подряд идущих друг за другом натуральных чисел, и кончая массивом из k подряд идущих друг за другом натуральных чисел от n - k + 1 до n, переписывается в очередное значение двумерного массива x, содержащего все сочетания из n элементов по k, число которых равно n!/(k! (n - k)!)

Алгоритм нахождения всех сочетаний без повторений  из n элементов по k элементов

Алгоритм нахождения всех размещений из n элементов по k.

Изначально массив y представляет собой пустой массив, а массив t представляет собой массив из k подряд идущих натуральных чисел от 1 до k. Начальное значение индекса массива p = 0.

В начале каждого цикла увеличиваем значение элемента t[p] на единицу до тех пор, пока не найдется такой t[p], которого нет в массиве y.

Если полученный таким образом элемент t[p] не превосходит числа n, то добавляем его в массив y, и если p = k, то k элементов массива y от y[0] до y[k - 1] включительно переписываются в очередное значение двумерного массива x, содержащего все размещения без повторений из n элементов по k, число которых равно n!/(n - k)!

В противном случае, если полученный элемент t[p] больше n, то значение элемента t[p] приравнивается единице, значение индекса p уменьшается на единицу, в массиве y остаются только элементы от y[0] до y[p-1] включительно, значение предыдущего элемента t[p] (после уменьшения индекса p на единицу) увеличивается на единицу.

После этого цикл повторяется до тех пор, пока значение p не станет меньше нуля.

Алгоритм нахождения всех размещений без повторений  из n элементов по k элементов

Метод .indexOf() не поддерживается в старых браузерах. Поэтому не следует писать while(y.indexOf(t[p] > -1)) t[p]++ вместо while (isInclude(y, t[p]) == true) t[p]++;

Медленный алгоритм нахождения размещений, сочетаний и сочетаний с повторениями.

В медленном алгоритме находятся все размещения с повторениями из n элементов по k элементов, число которых равно nk. Каждое такое размещение с повторениями записывается в массив y длины k.

Затем каждый массив y, представляющий собой размещение с повторением из n по k, сортируется по возрастанию.

Если ищутся размещения без повторений, то каждый отсортированный массив проверяется на равенство друг другу двух соседних элементов в нем. Если равных соседних элементов в отсортированном массиве нет, то первоначальный массив y, который был до сортировки, переписывается в очередное значение двумерного массива x, содержащего все размещения без повторений из n элементов по k, число которых равно n!/(n - k)!

Если ищутся сочетания с повторениями, то каждый отсортированный по возрастанию массив сравнивается с исходным массивом y. Если все элементы отсортированного массива длины k совпадают с элементами исходного массива y ( то есть, если исходный массив y уже был упорядочен по возрастанию, то массив y переписывается в очередное значение двумерного массива x, содержащего все сочетания с повторениями из n элементов по k, число которых равно (n + k - 1)!/(k! (n - 1)!)

Если ищутся сочетания без повторений, то, во-первых, каждый отсортированный массив проверяется на равенство друг другу двух соседних элементов в нем, и, во-вторых, каждый отсортированный по возрастанию массив сравнивается с исходным массивом y. Если равных соседних элементов в отсортированном массиве нет, и если все элементы отсортированного массива длины k совпадают с элементами исходного массива y, то массив y переписывается в очередное значение двумерного массива x, содержащего все сочетания без повторений из n элементов по k, число которых равно n!/(k! (n - k)!)

Примечание. Данный алгоритм действительно работает очень медленно. Например, для нахождения единственного сочетания из 9 по 9, надо будет отсортировать по возрастанию 99 = 387420489 размещений с повторениями и выбрать то единственное размещение с повторениями 123456789, которое, во-первых, не содержит одинаковых элементов, и, во-вторых, уже отсортировано изначально по возрастанию. Вероятно, ваш браузер надолго зависнет, если вы введете n = 9, k = 9 и нажмете на кнопку Сочетания.

Медленный алгоритм нахождения размещений, сочетаний и сочетаний с повторениями отбором упорядоченных и не имеющих повторений размещений с повторениями На главную страницу Яндекс икс