Полный перебор всех сочетаний элементов в массиве
Приветствую.
Подскажите, пожалуйста, по алгоритмике. Есть массив из 30-60 элементов (количество плавающее). Нужно перебрать все сочетания его элементов. При этом элементы в конечной строке не должны повторяться, а также повторяющиеся сочетания (при перестановке элементов) не должны учитываться, то есть 1+2+3+4 = 1+3+2+4 = 1+4+2+3 = 4+1+2+3 и т.д. - это всё одно и то же, повторы нужно игнорировать, оставить только один из них - например, 1+2+3+4. Расписал пример для 4 элементов: Вроде всего получается (количество элементов)^2 вариантов сочетаний. С 4-мя элементами всё просто, можно 4 цикла вложенных написать, но вот с 30-60 элементами это не выход. Может рекурсию какую-нибудь написать, не могу сообразить. Может кто делал на блице подобное? :rolleyes: UPD: вроде допёр, что от повторений можно избавиться переводом сочетаний в бинарную матрицу. 1 = 1000; 1+2 = 1100; 1+2+3 = 1110 ... 1+2+3+4 = 1111 То есть нужна бинарная матрица |
Ответ: Полный перебор всех сочетаний элементов в массиве
Капец как всё просто :-)
PHP код:
|
Ответ: Полный перебор всех сочетаний элементов в массиве
Да вот только незадача...
20 элементов перебирает за 1,7 сек 26 элементов за 2 минуты 30 элементов за 30 минут а 60 элементов за 61000 лет ::o" придется сокращать количество элементов до 26 |
Часовой пояс GMT +4, время: 06:21. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot