Algorytm dzielący odcinek na części

Question

Hej, postaram się jak najkrócej opisać problem. Zaciekawił mnie i zastanawia mnie jak to rozwiązać. Otóż mamy podany zbiór X (elementy mogą się w nim powtarzać), a my mamy symulować cięcie odcinka na takie fragmenty, że ich sumy długości pojedynczo, potem parami obok siebie, potem trójkami itd. dają razem ten pierwszy zbiór X. Matematyka przy okazji mówi, że z tego powodu X=A(A+1)/2, jeśli chodzi o liczbę elementów. Na pewno brzmi to enigmatycznie, więc wyjaśnię przykładem:
zbiór X = {2, 3, 3, 4, 6, 6, 7, 8, 9, 9, 11, 12, 15, 15, 18}, odpowiedź brzmi (na przykład, bo może ich być więcej, ale wystarczy jedna): (3, 4, 2, 6, 3). Widać, że to dobra odpowiedź, bo utworzymy takie zbiory (dla pojedynczych sum, sum dwójkami, trójkami itd.: {3, 4, 2, 6, 3}, {7, 6, 8, 9}, {9, 12, 11}, {15,15}, {18} (nota bene ostatni element to zawsze długość odcinka).

Dla zbioru X={1, 2, 3} nasza kombinacja będzie dwuelementowa (równanie X=A(A+1)/2) i jest postaci po prostu (1, 2).

No i mam problem, jak zaimplementować takie wyszukiwanie poprawnej kombinacji? Nie chodzi mi o kod, tylko chciałbym wytłumaczenie samego postępowania. Z góry dzięki za pomoc, a w razie pytań i niejasności służę wyjaśnieniami. Liczę, że znajdzie tu się dobry człowiek, który rozumie problem. :D

Answer 1

No to zapisujesz ten zbiór X do tablicy, tworzysz jakiś bufor, aby sprawdzić sumy pojedyncze, dwójki, trójki itd, i po prostu iterujesz po tej tablicy.

Comments

Nie do końca rozumiem, a w trakcie iteracji po tablicy kiedy rozwiązanie jest tworzone? Czy mówisz na razie o wstępnym znalezieniu odpowiednich liczb, a ich kolejność zostawić na później?

---

Czy mówisz na razie o wstępnym znalezieniu odpowiednich liczb, a ich kolejność zostawić na później?

Tak, właśnie to mam na myśli. 

---

No dobra, a pytanie jak wybierać te liczby? Kilka początkowych często jest obowiązkowych i nie trzeba decydować, po prostu muszą być w wyniku, ale co z resztą, co do których nie mamy pewności, że mają się pojawić w odpowiedzi?

---

sprawdzasz po kolei wszystkie kombinacje. Aby to zoptymalizować możesz też odrzucić niektóre kombinacje prostymi unstrukcjami warunkowymi.

---

Ja tu widzę jedynie taką optymalizację, że poszukiwanie można przerwać, gdy iterując po tablicy suma przekroczy długość odcinka (wartość ostatniego elementu zbioru X), przyspieszenia widzę podczas szukania odpowiedniej kolejności wynikowej kombinacji, ale gdy dopiero się wybiera elementy, to trudno mi zauważyć jeszcze jakieś warunki "ucinające" gałęzie rozwiązań.

Answer 2

Pomyśl najpierw jak byś to sam chciał zrobić, co robisz żeby rozwiązać ten, problem jak masz zadanie taki zbiór znaleźć. Na początek wybierasz jakieś liczby. Ty wybrałeś akurat 3,4,2,6,3. Następnie dodajesz pary i sprawdzasz, czy ten drugi ciąg, który z nich wyjdzie będzie podzbiorem X. Następnie bierzesz trójki itd. No to pozostaje ci już tylko wykombinować jak masz wybierać liczby do sprawdzenia i jak w miarę optymalnie sprawdzać.

Z wybieraniem liczb, no to najprościej sprawdzać każdą możliwą parę, czyli jak masz ten zbiór X podany, to wybierasz jego pierwszy element i dodajesz do drugiego, następnie sprawdzasz czy otrzymasz element zbioru X, jak tak to wybierasz sobie kolejny element i dodajesz do poprzedniego jak należy do X, to analogicznie, a jak nie należy to szukasz innego jak innego już nie ma, to usuwasz poprzedni element i szukasz nowego i analogicznie.

Comments

W sumie prosty i skuteczny sposób z tym wybieraniem liczb, tylko tak jeszcze myślę, czy to zadziała, gdy jakiś element jest sumą więcej niż 2 liczb. Wydaje mi się, że powinno być ok...

---

No to zakładamy, że masz ten zbiór X i znalazłeś już jakiś ciąg z dwójką na początku. Teraz znowu ustawiasz tą dwójkę na początku i robisz tak jak ci napisałem z tym, że dla drugiego elementu będzie szukać od pozycji większej niż pozycja elementu w zbiorze X, na drugim miejscu znalezionego wcześniej ciągu. I analogicznie.

Np. trzy pierwsze liczby ciągu który znalazłeś to 2,7,4 w zbiorze X={2,3,7,6,4,8,9}. Wówczas zaczynasz znowu od 2, więc twój ciąg obecnie to {2}, następnie od pozycji większej niż 7 sprawdzasz czy tworzyć będzie ten szukany ciąg. Czyli od 6 zaczynasz i jak 6 jest dobra no to masz już ciąg {2,6}.

 

Oczywiście tutaj te ciągi prawdopodobnie nie spełniają wymogów zadania, ale chodzi o sens zrozumienia problemu.

---

Ok, napisałem już generator podstawowych, niezbędnych liczb. Teraz mnie tylko zastanawia taki bardziej teoretyczny problem: czy danemu zbiorowi X odpowiada dokładnie jeden zbiór możliwych liczb? Czy może istnieją np. dwa różne zestawy liczb dające te same sumy? Intuicja podpowiada, że jest tylko jeden taki, ale wolałbym się upewnić.
No i jeszcze pozostaje problem optymalizacji: zauważyłem, że po wybraniu kilku początkowych, niezbędnych liczb możliwości wybrania pozostałych znacząco się zmniejszają (dla zdecydowanej większości kombinacji ich łączna suma jest większa od długości odcinka), ale dla większych instancji (|M|=12 (największa która ma przejść to |M|=15)) i tak liczba możliwych kombinacji wynosiła około 30 mln, jestem pewien, że da się jeszcze zauważyć jakąś własność, która zmniejszy pole przeszukiwań, tylko tego nie widzę. Byłbym bardzo wdzięczny za dodatkowe wskazówki.

---

Na początek sprawdzasz wszystkie kombinacje w których pierwszym elementem będzie element na pozycji 1 ze zbioru X, następnie 2, 3 i tak do końca. Nie wiem, czy jak masz jeden element należący do zbioru to go wypisujesz czy nie, według tego co napisałeś powinieneś go wypisać. Elementy w zbiorze X, mogą się powtarzać, ale elementy w tym twoim zbiorze już nie(Chodzi o to, że jak masz zbiór X={1,2,2} to ci nie wygeneruje ciągu 1,1,1, ale ciąg 2,2 już tak na przykład), takie rozwiązanie ma ten algorytm, bo o to ci chyba chodziło. Dla zbioru X o mocy 15 jest 15^15 możliwych kombinacji, lecz to nie znaczy, że będzie tyle rozwiązań. Zbiór X to ty wprowadzasz, a program jedynie generuje odpowiedni ciąg, który spełnia te założenia co napisałeś. Co do optymalizacji, to tego algorytmu już niezoptymalizujesz bardziej, ale możesz poczytać o permutacjach, może istnieje jakiś algorytm który będzie permutować twój zbiór dużo szybciej i efektywniej.

---

Niezbyt rozumiem, mówimy nadal o wyznaczaniu liczb do odpowiedzi, nie wyznaczaniu ich kolejności? Zauważyłem, że pierwsze dwie liczby ze zbioru X zawsze wpisujemy do wynikowego zbioru, bo pierwsza, naturalnie najmniejsza (nie da się jej stworzyć z innych), a druga, bo jeśli jest taka sama, to też jej nie stworzymy z innych, a z pierwszej nie możemy bo ona "tworzy" samą siebie, natomiast jak jest inna, to nie zostanie stworzona z pierwszej, która nie ma być jeszcze z czym zsumowana. Czyli w wyniku są pierwsze dwa elementy zbioru X. Tworzę z tych dwóch pierwszych elementów pomocniczy zbiór, powiedzmy S, który przechowuje wszystkie możliwe do uzyskania w tej chwili sumy, inicjuję go 3 elementami: 1. i 2. ze zbioru X i ich sumą. Potem sprawdzam kolejną liczbę, jeśli występuje w zbiorze S, to być może nie jest niezbędna (ale istnieje możliwość, że też musi być) i kończę algorytm wstępnego znajdowania niezbędnych liczb. Jeśli jednak liczba nie jest w zbiorze S (lub jest taka sama jak poprzednia), to tworzę nowy zbiór S' = S, dodaję do wszystkich jego elementów wartość obecnie rozpatrywanej liczby i tak otrzymany zbiór nadpisuję na stary S=S+S', dzięki temu zabiegowi mam wszystkie możliwe sumy, które do tej pory można otrzymać. Trochę zagmatwałem pewnie, ale właśnie tak to póki co robię i nie do końca rozumiem twój sposób.
Mógłbyś rozjaśnić mi o co chodzi z tymi ciągami dla zbioru {1,2,2}? Na marginesie to w sumie dla tego zbioru nie ma rozwiązania, dla takich (1,1) -> {1,1,2}, (1,2) -> {1,2,4}, ogólnie 3 element jest w tym przypadku sumą dwóch poprzednich.
Wybacz, że tak męczę, dla mnie ciężki temat i muszę to maksymalnie zoptymalizować, liczę że się nie poddasz. :D

---

Czyli w twoim zadaniu nie chodzi o znalezienie wszystkich ciągów, takich że w ciągu  nazwijmy go a, suma jego elementów odpowiednio a1 + a2 , a3+a4 itd da jakieś elementy ze zbioru początkowego X, następnie a1 + a2 + a3, a4+a5+a6 itd. również da jakieś elementy ze zbioru X i analogicznie aż do momentu gdy nie da się utworzyć takiego zbioru, a chodzi ci o znalezienie takiego ciągu, który w ten sposób da ci wszystkie elemnty, które należą do zbioru X tak?

---

Ach, musiałem głupio to napisać, chodzi o znalezienie takiego ciągu a, że zbiór X będzie postaci {a1, a2, a3, a4, ... , an, (a1+a2), (a2+a3), (a3+a4), ... , (a{n-1}+an), (a1+a2+a3), (a2+a3+a4), ... , (a1+a2+...+an)}.
Np. jeśli na wejściu jest zbiór {1,2,3} (zawsze rosnąco, bo to i tak tylko zbiór), to odpowiedzią jest ciąg (1,2), dla zbioru np. {1,2,3,7,8,8,10,15,16,18} jest ciąg (2,1,7,8). Te ciągi mogą być też w odwrotnej kolejności, sumy wyjdą te same.

---

Czyli chodzi o to co napisałem post wcześniej, więc wystarczy, że do tego algorytmu dopiszesz warunek sprawdzający znaleziony już ciąg, czy będzie on zawierał wszystkie elementy ze zbioru X. Co do twojego pytania na starcie, czy jak wyszukasz pierwszy to czy będzie to jedyny taki ciąg, no wydaje mi się, że przeważnie będzie to jeden, ale raczej nie zawsze. Co do optymalizacji samego algorytmu to ja nie widzę takiej możliwości, ale to nie znaczy że jej nie ma :P Mógłbyś sprawdzać, czy liczba nie wychodzi po za największy kolejny szukany element twojego zbioru X, lecz uprzednio musiałbyś ten zbiór X uporządkować.

---

No tak pewnie trzeba zrobić, ale teraz mnie naszła taka beznadziejna myśl: chciałem najpierw wyznaczyć liczby, a następnie ich kolejność, ale żeby sprawdzić czy te liczby są dobre, muszę je posumować już w dobrej kolejności, a to sugeruje zagnieżdżoną petlę, tj. dla każdego zestawu liczb muszę dodatkowo sprawdzić każdą jego permutację, a to chyba nie będzie za dobre... Dziwię się, że wcześniej nie zauważyłem tego problemu, chyba że go nie ma, a ja mam chwilowe zaćmienie...

---

Chcesz napisać program, który ci stworzy taki zbiór X? xD

---

No nie, ale żeby sprawdzić czy mam poprawne liczby wynikowe muszę sprawdzać czy tworzą zbiór zadany na wejściu, jak nie, to zmieniam chyba ich kolejność, a jak dla żadnej kolejności nie tworzą zbioru X, to wtedy chyba dopiero mogę stwierdzić, że szukam innych liczb. No nie wiem jak to prościej ugryźć... :(

---

Mogę stworzyć z uzyskanych liczb zbiór wszystkich potencjalnych elementów, z jakich mógłby się składać zbiór sum i sprawdzać czy zbiór X zawiera się w nim, ale to nie jest takie jednoznaczne, pozwala wykluczyć liczby, ale nie zatwierdzić je ze 100% pewnością.

---

Jeżeli będą zawierały wszystkie elementy zbioru X, to czemu to mogą być nie te liczby ??

---

Chodzi o to, że nawet jeśli zbiór X zawiera się w tym większym, to nie ma jednej kombinacji, dla której powstaje zbiór X. Np. wszystkie elementy zbioru X powstają, ale tylko w wyniku zsumowania wyników dla dwóch kombinacji jednocześnie. Np. (czysto teoretycznie) X = {1,2,4,5}, a dla dwóch kombinacji są zbiory {1,2,3,4} i {1,2,3,5}, w tym zbiorze potencjalnych sum będą zatem elementy 1,2,3,4,5, a więc zawierające zbiór X, ale żadna kombinacja sama, pojedyncza, tego nie spełni. Może moje rozumowanie jest błędne i czegoś nie widzę, ale tak mi się wydaje.

---

A jak uzyskasz zbiór 1,2,3,4 albo 1,2,3,5 ? Jeżeli 3 nie należy do X.

Po za tym, skąd te dwie sumy ? Jeżeli program wygeneruje ci ciąg trójelementowy a,b,c to a,b,c zawiera się w X , a+b , b+c - zawiera się w X , a+b+c - zawiera się w X. I jeśli są to wszystkie możliwe elementy zbiory X no to to jest twój ciąg.

---

W sumie to ten twój algorytm to sprowadza się do znalezienia takich liczb a1,a2,a3 ... an , że elementy ciągu X będą takie jak elementy ciągu:

{ a1,a2,a3 .... , an , a1+a2, a2+a3, a3+a4 ... an-1 + an , a1+a2+a3 , a2+a3+a4 ... , an-2 , an-1,an }

O chodzi tu tylko o elementy, nie o ich kolejność.

---

No właśnie problem jest z tym, że np. dla kolejności
(1,3,2) mamy zbiór X = {1, 2, 3, 3, 4, 6},
a dla kolejności
(1,2,3) jest już zbiór X = {1, 2, 3, 3, 5, 6}, dla większych instancji te zbiory różnią się znacznie bardziej,
no i problem jest jak szybko sprawdzić, że uzyskane liczby potrafią odtworzyć zbiór X, można po prostu sprawdzić wszystkie możliwe kolejności, ale jeśli co chwilę będziemy natrafiać na potencjalnie dobre liczby (suma całego odcinka się zgadza), będzie to bardzo wolne.

Wezmę jeszcze jeden przykład i pokażę jak działa algorytm:
X = {1,2,3,7,8,8,10,15,16,18}
Wybieram 1 i 2, będą należeć do wyniku. Przy 3 nie ma pewności, więc na razie stopujemy. Oczywiście liczb, które mamy znaleźć są cztery, bo wtedy liczba sum dwójek, trójek itd. się zgadza, tak więc mamy już 1 i 2. Zostały pozostałe dwie do znalezienia. Wykorzystujemy to, że łączna suma tych czterech liczb wynosi 18 (ostatni element X), więc pozostała suma (bez 1 i 2) to 15. Dodatkowa optymalizacja: biorąc nawet najmniejszy możliwy element tj. 3, wtedy elementu 15 już nie możemy wziąć, bo będzie za duża suma, czyli przeszukiwanie ograniczamy do zbioru {3,7,8,8,10}. Teraz sprawdzamy dwójki z tego zbioru, jeśli suma nie jest równa 15, to od razu idziemy do następnej, no i tak dochodzimy do pary (7,8) (być może są jeszcze jakieś inne - tutaj nie, w ogólności pewnie tak). Czyli mamy liczby: 1, 2, 7, 8.
Tutaj jest właśnie zasadniczy problem: jak sprawdzić, że to poprawne liczby? Póki co wiemy, że ich suma wynosi 18. Tworzą one w tej kolejności zbiór X' i niestety łatwo zauważyć, że nie ma w nim 10 (2 i 8 nie są koło siebie), a w oryginalnym zbiorze X jest.
I dlatego wpadłem na pomysł, że tworzymy z tych znalezionych liczb zbiór wszystkich możliwych sum S (nie tylko pary obok siebie, tj. 1-2, 2-7, 7-8, ale też 1-7, 1-8 itp.) i jeśli zbiór X się zawiera w S, to być może mamy dobre liczby. Ale że ten większy zbiór S jest jakby złożeniem wszystkich zbiorów X' dla każdej możliwej permutacji, to nie ma pewności, że da się uzyskać oryginalny zbiór X wyłącznie jedną kombinacją (póki co nie mogę znaleźć przykładu na potwierdzenie, może jestem w błędzie?).
Po prostu chcę uniknąć sytuacji, że mam tysiące potencjalnie dobrych zestawów liczb, i dla każdego zestawu robię tysiące permutacji, żeby się upewnić. Muszę jakoś to ominąć.

---

No tak jak mówiłem, to najprostszy sposób. Możesz spróbować, sprowadzić to do postaci macierzy i rozwiązać, czy coś w tym stylu, może będzie szybciej. No ale to już matematyka, jeżeli masz czas i chęci to możesz się w to pobawić.

Answer 3

Może ktoś się dołączy do debaty jak to zrobić? :D