Перестановки с повторениями: Комбинаторика в EXCEL

Подсчитаем в MS EXCEL количество перестановок с повторениями из n элементов. С помощью формул выведем на лист все варианты таких перестановок (английский перевод термина: permutations of multisets).


Напомним, что Перестановкой множества из n элементов называется расположение элементов в определенном порядке. Число Перестановок n элементов равно n! (факториал) (см. статью Перестановки без повторений: Комбинаторика в MS EXCEL ). Для вычисления факториала в MS EXCEL есть специальная функция ФАКТР() .

Обычно, перестановки рассматривают для множества с неповторяющимися элементами, например для {1; 2; 3; 4; 5; 6}. Всего перестановок в этом случае 6!=720. Вариантами перестановок являются  {1; 2; 3; 4; 5; 6};  {2; 1; 3; 4; 5; 6};  {5; 2; 3; 4; 1; 6};  {3; 2; 1; 5; 4; 6} и т.д., всего 720.

Если элементы множества повторяются, например, {1; 1; 1; 2; 4; 4}, то количество перестановок равно 6!/(3!1!2!) (6 – это общее количество элементов множества, 3 – это количество повторов числа 1; 1 – т.к. число 2 в единственном экземпляре, а 2 – это 2 повтора числа 4). Т.е. всего 60 перестановок, что существенно меньше, чем для того же количества элементов без повторений.

Для небольшого количества элементов в EXCEL возможно отобразить все варианты комбинаций с помощью всего нескольких формул. Например, для множества из 7 элементов {1; 1; 2; 2; 3; 3; 3} вариантов перестановки будет всего 210.

В файле примера организован вывод всех Перестановок с повторениями для заданного множества (максимум 7 элементов) и подсчет количества таких перестановок.

Также в файле примера даны рекомендации как увеличить количество элементов множества и на отдельном листе приведен пример увеличения множества с 7 до 8 элементов (указано какие столбцы добавлять и какие формулы копировать). Написания или изменения формул не требуется.

Перед увеличением количества элементов вычислите количество комбинаций, т.к. количество комбинаций очень быстро растет при росте размера множества элементов. Так для 15 элементов количество комбинаций превышает 1 триллион (если повторов нет). Фактически в книге EXCEL пределом будет размещение нескольких десятков тысяч комбинаций, т.к. в файле использованы ресурсоемкие формулы массива, вычисление которых требует времени.

Если множество состоит из букв, например, слово MISSISSIPPI, то можно подсчитать количество анаграмм (слов, состоящих из тех же букв): 11!/(1!4!4!2!) (11 – это общее количество букв, 1 – одна буква M; 4 – это 4 повтора буквы I, а вторая 4 – это 4 повтора буквы S, 2 – это 4 повтора буквы P).

Примечание : О Размещениях можно прочитать в статье Размещения без повторений: Комбинаторика в MS EXCEL , а о Сочетаниях в статье Сочетания без повторений: Комбинаторика в MS EXCEL .

Комментарии
Только для авторизованных пользователей

Аноним, 18 февраля 2016 г.
Добрый день уважаемый гуру, подскажите как в excel можно вывести шестизначный числовой ряд (их всего 729) из трёх цифр 1 2 3, которые могут повторяться.
Михаил, 14 июля 2016 г.
1. Сначала с помощью статьи http://excel2.ru/articles/sochetaniya-s-povtoreniyami-kombinatorika-v-ms-excel получаете все сочетания с повторениями из 3 по 6 (числа 1, 2 и 3 размещаются в 6 ячейках, всего 28 вариантов) 2.Берете каждый из этих 28 вариантов и последовательно подставляете в желтые ячейки в файле примера этой статьи. Их нужно последовательно копировать на отдельный лист. 3. Вы правы, всего получится 729 различных комбинаций.
Аноним, 17 марта 2018 г.
Здравствуйте Михаил! Подскажите какие формулы нужно изменить, если количество элементов 8.
Аноним, 22 июня 2020 г.
А можно аналогичный файл только что б было больше количество элементов?
Михаил, 22 июня 2020 г.
больше это сколько?
Аноним, 7 июля 2020 г.
[id295933596|Михаил], ну штук 15-20
Михаил, 7 июля 2020 г.
[id15355643|Илья], для 15 элементов будет больше 1 триллиона комбинаций (если все элементы разные). На лист EXCEL помещается 1 048 576 значений. Понадобится 1 млн. столбцов и суперкомпьютер )). Но здравое зерно есть, я напишу в статье как увеличить число элементов, скажем до 10.
Михаил, 9 июля 2020 г.
[id15355643|Илья], я обновил файл примера, включил новый лист с рекомендациями как добавлять элементы (см. второй лист). Для 8 элементов и 1680 комбинаций пересчет формул занимает несколько секунд.
Аноним, 17 июля 2020 г.
[id295933596|Михаил], Хорошо. Большое спасибо)
(только для авторизованных пользователей)

© Copyright 2013 - 2020 Excel2.ru. All Rights Reserved