Poszukuję algorytmu rekurencyjnie łączącego obiekty

Witam!

Zacznę od przykładu, bo tak najłatwiej będzie mi przedstawić problem.

Mamy zbiór obiektów (powiedzmy: [A,B,C]). Obiekty można łączyć ze sobą, przy czym:

• A + B == B + A
• (A + B) + C != A + (B + C) != (A + C) + B

Chciałbym wygenerować wszystkie możliwe połączenia (w tym przypadku (A+B), (A+B)+C, (A+C), (A+C)+B, (B+C), (B+C)+A), ale najprostszy algorytm (czyt. bruteforce) generuje (jak łatwo się domyślić) dużo powtarzających się kroków i co za tym idzie - zaczyna mieć duże problemy przy 9 obiektach (coś ok. 140 milionów połączeń).

Czy istnieje jakiś algorytm, który działałby szybciej (tzn. nie generował powtarzających się kroków)?

Tzn chcesz po prostu wykonać każde możliwe nawiasowanie dla każdej możliwej permutacji tej wejściowej listy? Co to dla ciebie są "powtarzające sie kroki"?

1. Tak

2. Przedstawię to na 4-elementowym przykładzie (A, B, C, D). Najprostszy algorytm zadziała tak:

3. (A+B)

4. ((A+B)+C)

5. ((A+B)+C)+D

6. ((A+B)+D)

7. ((A+B)+D)+C
   ##(A+B) (C+D)

8. (A+B)+(C+D)

9. (A+C)

10. ((A+C)+B)

11. ((A+C)+B)+D

12. ((A+C)+D)

13. ((A+C)+D)+B
    ##(A+C) (B+D)

14. (A+C)+(B+D)

15. (A+D)

16. ((A+D)+B)

17. ((A+D)+B)+C

18. ((A+D)+C)

19. ((A+D)+C)+B
    ##(A+D) (B+C)

20. (A+D)+(B+C)

21. (B+C)

22. ((B+C)+A)

23. ((B+C)+A)+D

24. ((B+C)+D)

25. ((B+C)+D)+A
    ##(B+C) (A+D)

26. (B+C)+(A+D)

27. (B+D)

28. ((B+D)+A)

29. ((B+D)+A)+C

30. ((B+D)+C)

31. ((B+D)+C)+A
    ##(B+D) (A+C)

32. (B+D)+(A+C)

33. (C+D)

34. ((C+D)+A)

35. ((C+D)+A)+B

36. ((C+D)+B)

37. ((C+D)+B)+A
    ##(C+D) (A+B)

38. (C+D)+(A+B)

Niektóre kroki (np. 1.3 i 6.3 czy 2.3 i 5.3) są takie same i co za tym idzie całe 'drzewo' wyników 'pod nimi' również - czyt. niepotrzebne powtórzenia. W przypadku 4 obiektów jest to tylko 6 zbędnych połączeń, ładniej to widać przy większej ich liczbie, ale myślę, że widzisz w czym problem.

Ok teraz widzę, czyli są przemienne ale nie są łączne. Niestety nie widzę za bardzo metody na generowanie tego bez takich "powtórzeń".

Nawet jeśli istniałaby jakaś w miarę łatwa metoda na unikanie takich powtórzeń, to i tak nie pomoże na wykładniczą złożoność problemu. Być może zamiast przy n=9, problematyczne byłoby n=10, ale i tak intuicja podpowiada mi, że nie.

Niby tak, ale dla każdej większej liczby różnica robi się coraz większa - dla 5 zamiast 430 będzie to 220 unikalnych połączeń.
Dodatkowo nie liczę tutaj na podniesienie granicy do jakiejś kosmicznej wartości, już wyniki rzędu 20 by mnie ratowały. :-)