[Przegrywek123]

Elo. Załóżmy że mam n-elementowy zbiór (listę) i muszę z niej policzyć możliwe k-elementowe kombinacje bez powtórzeń. Np dla
n = {1,2,3,4,5,6} i k = 3 będzie to {1,2,3 }; {1,2,4}; {1,2,5};{3,4,6} etc. Elementy zbioru nie mogą się powtarzać {1,1,2} == błąd.
O ile policzenie ilości kombinacji jest stosunkowo proste (n!) / (k!(n-k)) , to jak je wszystkie uzyskać i zapisać jako osobną listę?
#programowanie #java #algorytmy #matematyka #naukaprogramowania

[v.....l]

#!$%@? rekurencyjnie

[L.....G]

@Przegrywek123: tak dla pewnosci. Zbior 1 2 3 jest rozny od 3 2 1 ?

[villager]

@Przegrywek123: np. http://sebastianpawlak.com/pl/Informatyka/Algorytmy/Permutacje/index.html ?

[Przegrywek123]

@LowcaG: a właśnie, niesprecyzowałem.
zbiory są równe jeśli zawierają te same elementy. Nie chodzi mi o derangement (nieporządek chyba)

[L.....G]

właśnie, niesprecyzowałem.

zbiory są równe jeśli zawierają te same elementy. Nie chodzi mi o derangement (nieporządek chyba)

@Przegrywek123: no to jezeli mniej niz 64 elementy to zwykle bity. Czyli np. 64 liczby to caly long(czyli w chu ) i sprawdzasz bity i bit mowi o tym czy liczba jest w zbiorze czy nie

[Przegrywek123]

@villager: to są przekształcenia permutacyjne, mi chodzi o kombinacje bez powtórzeń.
@LowcaG: możesz szerzej opisać? Tzn nie wiem w dalszym ciągu jak utworzyć z tej kombinacji nową tablicę.

[Satyrr]

elementytab = [1,6,8,2,76]
kombinacjetab = []
k = 3

wyznaczpermutacje(elementidx, zbior):
if |zbior| == k:
kombinacjetab.add(zbior)

if elementidx == k:
return

nowyzbiorzelementem = zbior.copy()
nowyzbiorzelementem.add(elementytab[elementidx])

wyznaczpermutacje(elementidx+1, zbior)
wyznaczpermutacje(elementidx+1, nowyzbiorzelementem)

wyznaczpermutacje(0, [])

Coś w tym stylu powinno zadziałać. Przy czym ma to sporą złożoność (O(2^k))

[L.....G]

@Przegrywek123: (jestem na imprezie wiec w skrocie)masz np. 5 elementow na wejsciu, czyli 5 bitow. Czyli mozliwe 32 zbiory( jezeli pusty to tez zbior).

No to zwykla iteracja od zera(albo jedynki)

O kurcze zrabalem nie zauwazylem, ze k elemntowe myslalem ze wszystkie. (No tak impreza :/ ) no dobra widze ze ktos ci napisal jakas odpowiedz.

[Satyrr]

@Satyrr: Usunęły mi się tabulatory, tu masz bardziej czytelnie https://pastebin.com/w36xLQWk

edit: wyznaczpermutacje powinno nazywać się wyznaczkombinacje oczywiście,
a zamiast if elementidx == k powinno być if elementidx == |elementy|

[krasnoludkolo]

@Przegrywek123 musisz to pisać sam czy chcesz gotowe?

[Przegrywek123]

@krasnoludkolo: jak masz to daj xD Próbuję przepisać wzorując na @Satyrr ale opornie idzie xD

[krasnoludkolo]

@Przegrywek123 nie mam, ale z tego co kojarzę to biblioteka vavr ma

[Przegrywek123]

@krasnoludkolo: To tak nie mogę ( ͡° ʖ̯ ͡°)

[krasnoludkolo]

@Przegrywek123 Tak oni to robią ale nie wiem czy pomoże :(
https://github.com/vavr-io/vavr/blob/master/vavr/src/main/java/io/vavr/collection/List.java#L1951

[Przegrywek123]

@krasnoludkolo: niestety, za dużo funkcji wewnętrznych żebym to zrozumiał :/
Doszedłem już do wypisania tych kombinacji, ale się powtarzają xD Zrobię to aproksymacyjnie, bo brute-force mnie przerasta XD

[krasnoludkolo]

@Przegrywek123 a ma być optymalnie?

[krasnoludkolo]

@Przegrywek123
https://www.sanfoundry.com/java-program-generate-all-possible-combinations-given-list-numbers/

Zamiast do listy dodawaj je do setu który na końcu zmień na listę

[Przegrywek123]

@krasnoludkolo: żeby stacka tylko nie wywaliło przez rekurencję za mocną xD Tak to moze (i będzie na pewno) O(2^k)

[Satyrr]

https://ideone.com/pNLD9m Tutaj jest poprawiona wersja algorytmu, bez powtórzeń. Wystarczyło przenieść if-a :P