Быстрый способ подбора всех возможных вариаций значений массива какие есть способы?

Question

[MasterCopipaster]

Доброе время суток, у меня есть массив из 3 элементов
Я хочу получить все возможные комбинации из этого массива:

массив: 'A','B','C' 
Комбинации:
A
B
C
A B
A C
B C 
A B C

Беда в том что у меня этот массив 179 элементов, и перебрать все возможные комбинации методом простого перебора не получается (слишком много времени требуется) есть ли алгоритмы позволяющие сделать это не методом простого перебора вариантов?

Comments

[Lynn «Кофеман»]

Эээ? А вы хоть представляете сколько всего вариантов? Тут по любому тепловая смерть вселенной раньше наступит

[MasterCopipaster]

Lynn «Кофеман», представляю поэтому и спрашиваю как это можно сделать быстро

[Lynn «Кофеман»]

Никак.
Ну никак невозможно перебрать 2^179 элементов за разумное время.

[Дмитрий]

MasterCopipaster, Видимо все же не представляете. Речь о том, что это вообще невозможно сделать. Только наборы элементов будут 2 в степени 179 и это не считая всех перестановок в наборах. Это сверхкосмические числа, нет компьютеров, у которых хватит на это памяти и непонятно зачем вам это надо.

[Adamos]

Поскольку решение чудовищно велико, очевидно, что на самом деле оно не требуется. Просто неверно поставлена задача. Скорее всего, решение - какой-нибудь банальный рюкзак, просто ТС о нем не слышал.

[xmoonlight]

Adamos, Это не рюкзак)))

[Adamos]

xmoonlight, задачи, решения которых нет вовсе (типа быстрого пересчета криптографии, построенной именно на сложности вычислений) я в качестве вариантов просто не рассматривал.

[xmoonlight]

Adamos, Тут проще, чем рюкзак)))

[Antonio Solo]

>> Я хочу получить все возможные комбинации из этого массива:

если ты хочешь получить все возможные комбинации - то это перебор

а если ты хочешь что-то другое - то и формулируй вопрос нормально

[Gip]

а ведь в этом массиве будут ответы на все вопросы. автор, не останавливайся!

[Arris]

7,66e+53 вариантов. Ну, приблизительно.

Проблема даже не в том, что просто перебор займет примерно 5*10^36 лет. Ну, если взять 5ггц проц...

Проблема в том, что всей энергии Солнца не хватит, чтобы просто сохранить все возможные состояния этого набора

[Robur]

Gip, потом придет на тостер с вопросом "как в массиве найти нужные строки, не перебором"?

[Денис Юрьев]

Robur, мы это уже не застанем =)

[Денис Юрьев]

Antonio Solo,

если ты хочешь получить все возможные комбинации - то это перебор

автор даже не представляет, на сколько это перебор

[Сергей П]

Денис Юрьев, да уж, взрыв мозга. комбинаторный

Answer 1

[Сергей П]

Судя по постановке задачи и примеру, речь идёт не о всех возможных начениях массива, а обо всех возможных подмножествах множества мощностью 179.
Если каждый элемент надмножества может либо входить, либо не входить, то кажое из множеств можно сопоставить с 179-битным двоичным числом. Очевидно, что таких чисел 2^179. Если убрать из набора пустое множество (в примере его не было), то вариантов станет на один меньше: 2^179-1.
В десятичной системе это вот столько вариантов: 766247770432944429179173513575154591809369561091801087

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

Но задачу-то решать как-то надо. Давайте воспользуемся кодом Грея, чтобы можно было при переходе от варианта к варианту ограничиться изменением всего лишь одного бита. Но и это не поможет нам перебрать все варианты за разумное время.
Пусть на один вариант нам потребуется безумно мало времени: один такт процессора. Сохранять мы варанты никуда не будем (потребовалось бы десять Юпитеров, чтобы на их атомах записать все варианты), просто покажем на экране. Да, за один такт этого не получится, но предсьавим себе что у нас такой специальный процессор с частотой 3 гигагерца. И нам потребуется 8099185802817355231125623242284335104 лет его работы.
И всё это бессмысленно. Протсо автор вопроса не понимает чего хочет.

Comments

[MasterCopipaster]

Ну дак умный человек спросит знающих людей прежде чем признает что задача не выполнима :)

[xmoonlight]

MasterCopipaster, правда я не понял цель перебора и цель получения всех комбинаций.
Зачем перебирать СТОЛЬКО?!
Задачу какую решаете?

[Сергей П]

xmoonlight, написано же... ну вот хочется ему и всё.

[xmoonlight]

Сергей Паньков, просто сбилдить варианты - бессмысленная задача.

[Сергей П]

xmoonlight, да согласен, согласен. конено бессмсленная. Как, впрочем, многие абстрактные задачи.
Вот, скажем, если бы он задачу укладки рюкзака таким перебором решить пытался, оно б понятно стало.

[xmoonlight]

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

[Сергей П]

xmoonlight, зачем?
Каждое подмножество взаимооднозначно сопоставляется с двоичным числом. Каждый бит показывает есть элемент в подмножестве или нет. Зачем решетку? Все эелементы все равно не сохранить.

[xmoonlight]

Сергей Паньков, чтобы не перебором всё делать, а сразу возрастающим покрытием.

[Сергей П]

xmoonlight, что значит возрастающим покрытием? покрытием чего?
в задаче же не указана причина перебора.
Может быть такая задача, в которой полный перебор никак не оптимизировать.

[xmoonlight]

Сергей Паньков, покрытием вариантов перебора при одном "шаге" рекурсии.
Как пример подобного: 1^1, 2^2, 3^3, 4^4, 5^5 => это 5 шагов рекурсии, и т.д.