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
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
@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ę.
@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.
@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
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
Komentarz usunięty przez moderatora
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
@LowcaG: możesz szerzej opisać? Tzn nie wiem w dalszym ciągu jak utworzyć z tej kombinacji nową tablicę.
kombinacjetab = []
k = 3
wyznaczpermutacje(elementidx, 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.
edit: wyznaczpermutacje powinno nazywać się wyznaczkombinacje oczywiście,
a zamiast if elementidx == k powinno być if elementidx == |elementy|
https://github.com/vavr-io/vavr/blob/master/vavr/src/main/java/io/vavr/collection/List.java#L1951
Doszedłem już do wypisania tych kombinacji, ale się powtarzają xD Zrobię to aproksymacyjnie, bo brute-force mnie przerasta XD
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ę