forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   2D-программирование (http://forum.boolean.name/forumdisplay.php?f=13)
-   -   Полный перебор всех сочетаний элементов в массиве (http://forum.boolean.name/showthread.php?t=20108)

DarkInside 04.12.2015 21:31

Полный перебор всех сочетаний элементов в массиве
 
Приветствую.
Подскажите, пожалуйста, по алгоритмике.
Есть массив из 30-60 элементов (количество плавающее). Нужно перебрать все сочетания его элементов. При этом элементы в конечной строке не должны повторяться, а также повторяющиеся сочетания (при перестановке элементов) не должны учитываться, то есть 1+2+3+4 = 1+3+2+4 = 1+4+2+3 = 4+1+2+3 и т.д. - это всё одно и то же, повторы нужно игнорировать, оставить только один из них - например, 1+2+3+4.
Расписал пример для 4 элементов:
1) - (пусто)
2) 1
3) 1+2
4) 1+2+3
5) 1+2+3+4
6) 1+2+4
7) 1+3
8.) 1+3+4
9) 1+4
10) 2
11) 2+3
12) 2+3+4
13) 2+4
14) 3
15) 3+4
16) 4

Вроде всего получается (количество элементов)^2 вариантов сочетаний. С 4-мя элементами всё просто, можно 4 цикла вложенных написать, но вот с 30-60 элементами это не выход. Может рекурсию какую-нибудь написать, не могу сообразить.
Может кто делал на блице подобное? :rolleyes:

UPD: вроде допёр, что от повторений можно избавиться переводом сочетаний в бинарную матрицу. 1 = 1000; 1+2 = 1100; 1+2+3 = 1110 ... 1+2+3+4 = 1111
То есть нужна бинарная матрица

DarkInside 04.12.2015 23:11

Ответ: Полный перебор всех сочетаний элементов в массиве
 
Капец как всё просто :-)

PHP код:

Function calc_k (n%)
    
    For 
1 To n%
        
end_str$ = end_str$ + "1"
    
Next
    
    
While str_t$ <> end_str$
        
        
str_t$ = Bin$(a_dec)
        
        If 
Len(str_t$) > nThen
            str_t
$ = Right (str_t$, n%)
        ElseIf 
Len(str_t$) < n
            While 
Len(str_t$) < n%
                
str_t$ = "0" str_t$
            
Wend
        
EndIf

a_dec a_dec 1
        
        
; ----- действие
        
    Wend
    
End 
Function 

Подставляем порядковые номера элементов в массивах вместо единичек и готово :super: Количество вариантов в итоге равно не (кол-во элементов)^2, а 2^(кол-во элементов) ...может пригодится кому...

DarkInside 05.12.2015 01:02

Ответ: Полный перебор всех сочетаний элементов в массиве
 
Да вот только незадача...
20 элементов перебирает за 1,7 сек
26 элементов за 2 минуты
30 элементов за 30 минут
а 60 элементов за 61000 лет ::o"

придется сокращать количество элементов до 26


Часовой пояс GMT +4, время: 13:48.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot