[Goglez]

Mam zbiór elementów, które oznaczam numerami 1,2,3,4,5 (to przykład, może być ich więcej). Dla tych elementów istnieje (2^n)-1 kombinacji bez powtórzeń (bez pustego, bo ten w tym przypadku nie ma sensu). Kombinacje generuję w następującym porządku:
i = indeks, k = wybrane elementy, a = k zapisane binarnie

i: 1; k: 1; a: 10000
i: 2; k: 2; a: 01000
i: 3; k: 3; a: 00100
i: 4; k: 4; a: 00010
i: 5; k: 5; a: 00001
i: 6; k: 12; a: 11000
i: 7; k: 13; a: 10100
i: 8; k: 14; a: 10010
i: 9; k: 15; a: 10001
i: 10; k: 23; a: 01100
i: 11; k: 24; a: 01010
i: 12; k: 25; a: 01001
i: 13; k: 34; a: 00110
i: 14; k: 35; a: 00101
i: 15; k: 45; a: 00011
i: 16; k: 123; a: 11100
i: 17; k: 124; a: 11010
i: 18; k: 125; a: 11001
i: 19; k: 134; a: 10110
i: 20; k: 135; a: 10101
i: 21; k: 145; a: 10011
i: 22; k: 234; a: 01110
i: 23; k: 235; a: 01101
i: 24; k: 245; a: 01011
i: 25; k: 345; a: 00111
i: 26; k: 1234; a: 11110
i: 27; k: 1235; a: 11101
i: 28; k: 1245; a: 11011
i: 29; k: 1345; a: 10111
i: 30; k: 2345; a: 01111
i: 31; k: 12345; a: 11111

Jak mając indeks i dowiedzieć się którą kombinację on oznacza, przy założeniu że nie chcę generować wszystkich innych żeby przejrzeć listę?

#programowanie #naukaprogramowania #matematyka #csharp

[tyrytyty]

@Goglez: sprawdzaj bity liczby

[Goglez]

sprawdzaj bity liczby

@tyrytyty: Tzn?

[tyrytyty]

@Goglez: masz indeksy od 0 do 31. W systemie dwójkowym przedstawisz je jako liczby od 0 do 11111. To czy na danej pozycji jest 0 czy 1 niech zależy od tego czy w kombinacji występuje element o tym numerze.

Zobacz że np k15 to 10001, masz 1 na 1 i 5 miejscu. K234 to 01110, 1 na 2 3 i 4 miejscu.

[Goglez]

@tyrytyty: To że "k" i "a" to jest to samo to wiem i napisałem to we wpisie. Ja chcę "i" przełożyć na "k" albo "a". "k" i "a" to jest to samo, dałem dwie kolumny dla wygody tylko. "k" to nie liczba 15, tylko wybrane elementy 1 i 5, w sumie mój błąd że nie dałem tam jakiegoś znaku do oddzielenia.

Przykład: dla i == 19 wybrane elementy to 1,

[fizyk20]

@Goglez: A jest istotne, żeby to był taki porządek, czy inny też da radę? Bo najłatwiej byłoby zapisać i binarnie, tak jak @tyrytyty zasugerował, a potem brać te elementy, na których pozycji w zapisie binarnym jest 1 - tylko że to da nieco inny porządek kombinacji.

[3denos]

Przeciez w tym przykladzie to sie nie zgadza: i: 3; k: 3; a: 00100, k to nie jest binarne a.

[fizyk20]

@Goglez: A jeśli istotny jest taki porządek, to możesz skorzystać z faktu, że posortowałeś sobie kombinacje po liczbie elementów (najpierw 1-elementowe, potem 2-elementowe itd.). Kombinacji k-elementowych jest n!/(k!(n-k!)) - stąd możesz szybko wyliczyć z i ile będzie elementów i indeks kombinacji spośród k-elementowych. Dalej możesz już wygenerować tylko kombinacje k-elementowe i znaleźć odpowiednią, choć tu pewnie też da się wymyślić optymalizację.

[Goglez]

Przeciez w tym przykladzie to sie nie zgadza: i: 3; k: 3; a: 00100, k to nie jest binarne a.

@3denos: k: 3 czyli w tym podzbiorze jest tylko element o numerze 3, a "a" to ciąg wszystkich elementów i jedynka oznacza który element został wybrany, np 00110 oznacza podzbiór z dwoma (dwie jedynki) elementami z pięciu (pięć cyfr) o numerach 3 i 4.

@fizyk20: Porządek jest istotny, ale słuszna

[Goglez]

To się wydaje działać tak jak oczekuję.

https://stackoverflow.com/a/11232567/12020205

@Goglez: Albo i nie, jednak nie wiem jak odwrócić proces, uzyskać kombinację z indeksu.

[fizyk20]

@Goglez: Spróbuj tego: https://pastebin.com/xByrbyub