[C++] Wariacja - liczby wkładane do pudełek
Ostatnio zmodyfikowano 2014-12-29 20:33
ziombel3 Temat założony przez niniejszego użytkownika |
[C++] Wariacja - liczby wkładane do pudełek » 2014-12-23 16:09:19 Witam. Mam problem z napisaniem programu który ma rozwiązać dany problem: Mamy k pudełek oraz n liczb. Należy wygenerować wszystkie możliwe kombinacje przydziału liczb do pudełek. Wszystkie liczby mają być przydzielone do jakiegoś pudełka. Inaczej formułując problem można powiedzieć, że dla każdej liczby przydzielamy pudełko. Jest k^n możliwości. Umiem wygenerować jedną wariancję dla k pudełek lub wszystkie wariacje dla jednego pudełka. Jak zrobić to z n pudełkami? Jak będzie wyglądał taki program? Dla k=2 i liczb 1,2,3 mamy:
1,2,3 1,2 1 3 1,2
3 2,3 1,2,3 1,2 3
Wiem, że mógłbym robić losową wariancję i jeśli jest unikalna to dodać ją do tablicy, która miała by wielkość k^n. Ale takie rozwiązanie oznaczało by olbrzymie obciążenie i to nie wchodzi w grę. |
|
DejaVu |
» 2014-12-29 20:33:05 std::vector < int > pudelka;
pudelka.reserve( k );
for( size_t i = 0; i < k; ++i )
pudelka.push_back( liczby[ i ] );
Potem wymieniaj liczby w ostatnim pudełku aż do wyczerpania wszystkich pozostałych liczb. Jak się wyczerpią wszystkie opcje na ostatnim pudełku to zmodyfikuj zawartość przedostatniego pudełka i znowu powtórz wszystkie możliwe liczby jakie można wpakować do pudełka ostatniego. Potem to zapętlasz i dostajesz wszystkie wyniki. |
|
| « 1 » |