Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование игр для компьютеров > Blitz3D > 2D-программирование

2D-программирование Вопросы, касающиеся двумерного программирования

Ответ
 
Опции темы
Старый 04.12.2015, 21:31   #1
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений
(для 369 пользователей)
Полный перебор всех сочетаний элементов в массиве

Приветствую.
Подскажите, пожалуйста, по алгоритмике.
Есть массив из 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 элементами это не выход. Может рекурсию какую-нибудь написать, не могу сообразить.
Может кто делал на блице подобное?

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

Последний раз редактировалось DarkInside, 04.12.2015 в 23:12.
(Offline)
 
Ответить с цитированием
Старый 04.12.2015, 23:11   #2
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений
(для 369 пользователей)
Ответ: Полный перебор всех сочетаний элементов в массиве

Капец как всё просто

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 
Подставляем порядковые номера элементов в массивах вместо единичек и готово Количество вариантов в итоге равно не (кол-во элементов)^2, а 2^(кол-во элементов) ...может пригодится кому...

Последний раз редактировалось DarkInside, 05.12.2015 в 00:47.
(Offline)
 
Ответить с цитированием
Старый 05.12.2015, 01:02   #3
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений
(для 369 пользователей)
Ответ: Полный перебор всех сочетаний элементов в массиве

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

придется сокращать количество элементов до 26
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


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


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com