Wszystkie możliwe kombinacje
Widzisz archiwalną wersję wątku "Wszystkie możliwe kombinacje" z forum pl.comp.lang.pascal
podlak
Witam,
jak zapisać pętlę, która z dostępnych elementów (np. liczb,
znaków..) układa wszystkie możliwe kombinacje.
Np dla zbioru znaków {a,b,c} jak zapisać pętlę, która zwróci:
a, ab, abc, b, bc, c, ac.
Oczywiście elementów będzie dużo więcej i jest ich niestała
liczba (1,2,3...,n).
Solaris
Dnia pańskiego 16 Jul 2006 12:06:36 -0700

: Witam,
: jak zapisać pętlę, która z dostępnych elementów (np. liczb,
: znaków..) układa wszystkie możliwe kombinacje.
: Np dla zbioru znaków {a,b,c} jak zapisać pętlę, która zwróci:
: a, ab, abc, b, bc, c, ac.
: Oczywiście elementów będzie dużo więcej i jest ich niestała
: liczba (1,2,3...,n).

Poczytaj o permutacjach.
Chyba było o tym ostatnio.

webmajste...@poczta.onet.pl

Witam,
jak zapisać pętlę, która z dostępnych elementów (np. liczb,
znaków..) układa wszystkie możliwe kombinacje.
Np dla zbioru znaków {a,b,c} jak zapisać pętlę, która zwróci:
a, ab, abc, b, bc, c, ac.
Oczywiście elementów będzie dużo więcej i jest ich niestała
liczba (1,2,3...,n).


to co szukasz to permutacja z powtorzeniami  (  przydatne hasla to tez
kombinatoryka , wariacja )  w google muisz szukac  pod

google.pl | webmajsterek ( to ja ) + pascal + permutacja  

powinines otrzymac wynik  linka -- z  postem mojego atorstwa
(
http://groups.google.pl/group/pl.comp.lang.pascal/browse_frm/thread/a...
4af9/1598f441b091ab87?
lnk=st&q=webmajsterek+pascal&rnum=8&hl=pl#1598f441b091ab87 )

jak wywolasz ta procedure z wartoscia permutation  ustawiona  na flase to
otrzymasz wszystkie mzoliwe kombinacje daego  zbioru ( zbior musi na wejsciu
bec posrtowany  rosnac )  .

muisz jedynie zminic kilka wierszy  --- bo teraz w takiej postaci program  leci
az do ktoregos wenetrznego wywolania rekurenkcyjne procedury i dopeiro wtedy
wypisuje ciag .

no i nie przesadzaj z wielkoscia n -- bo wynikow dla n elemntowego zboiru jest
n!

Andrzej Grażyński

to co szukasz to permutacja z powtorzeniami


Nie. To są KOMBINACJE.

Poza tym nie ma czegoś takiego jak permutacja powtórzeniami. Permutacja
powstaje w wyniku zmiany kolejności wyrazów ciągu.

Są za to wariacje z powtórzeniami i wariacje bez powtórzeń.

podlak

to co szukasz to permutacja z powtorzeniami  (  przydatne hasla to tez
kombinatoryka , wariacja )  w google muisz szukac  pod
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl


Z tego co mi wiadomo permutacja polega na przestawianiu elementów, w w
tym przypadku chodzi o ustawienie elementów w dowolnej kolejności i w
dowolnej licznie tych elementów.
To nie jest permutacja. A powtórzenia są dla wariacji.

podlak

| to co szukasz to permutacja z powtorzeniami

Nie. To są KOMBINACJE.


kombinacje polegają na wyborze k elementów z n elementów, a tu k
może być od 1do n i nie jest zdefiniowane. Kobinacja to to też nie
jest.

argothiel

| to co szukasz to permutacja z powtorzeniami  (  przydatne hasla to tez
| kombinatoryka , wariacja )  w google muisz szukac  pod
| Wysłano z serwisu OnetNiusy: http://niusy.onet.pl

Z tego co mi wiadomo permutacja polega na przestawianiu elementów, w w
tym przypadku chodzi o ustawienie elementów w dowolnej kolejności i w
dowolnej licznie tych elementów.
To nie jest permutacja. A powtórzenia są dla wariacji.


Bez obrazy, ale bzdury gadacie :)
Istnieją permutacje, wariacje i kombinacje z powtórzeniami i bez.
Permutacja polega na przestawianiu elementów i w tworzonych ciągach
zawsze jest n elementów (tyle ile jest wszystkich elementów).

W permutacjach bez powtórzeń wszystkie elementy są różne.
Wzór na liczbę permutacji bez powtórzeń to n!.
Przykład: mamy zbiór A={a,b,c}
Możliwe podzbiory to: {abc, acb, bac, bca, cab, cba}

W permutacjach z powtórzeniami mamy k elementów, które się
powtarzają odpowiednio n1, n2, ..., nk razy.
Suma n1 + n2 + ... + nk = n
Wzór na liczbę możliwych zestawień to:
n!/(n1!*n2!*...*nk!)
Przykład: mamy zbiór A={a,c}. Pierwszy element powtarza się 2 razy,
drugi 1 raz.
Możliwe podzbiory to: {aac, aca, caa}

W kombinacjach ze zbioru n elementów wybieramy k<=n elementów.
A w wariacjach podobnie jak w kombinacjach, tylko kolejność
jest istotna.
Dla zbioru A = {a, b, c} i k = 2 mamy:

Kombinacje bez powtórzeń:
{ab, ac, bc}

Kombinacje z powtórzeniami:
{ab, ac, bc, aa, bb, cc}

Wariacje bez powtórzeń:
{ab, ba, ac, ca, bc, cb}

Wariacje z powtórzeniami:
{ab, ba, ac, ca, bc, cb, aa, bb, cc}

A w zadaniu chodzi oczywiście o zbiór wszystkich podzbiorów,
który nie zalicza się do żadnej z powyższych grup. Można jednak
potocznie go nazwać zbiorem wszystkich kombinacji, gdyż jest on
równoważny sumie kombinacji po 0, po 1, ..., po n.

Pozdrawiam, argothiel

podlak

Istnieją permutacje, wariacje i kombinacje z powtórzeniami i bez.
1, ..., po n.

Pozdrawiam, argothiel


Krótko mówiąc problem nie jest kombinacją,  wariacją czy
permutacją. :)

Andrzej Grażyński


| to co szukasz to permutacja z powtorzeniami
| Nie. To są KOMBINACJE.

kombinacje polegają na wyborze k elementów z n elementów, a tu k
może być od 1do n i nie jest zdefiniowane. Kobinacja to to też nie
jest.


Kombinacja k-elementowa jest k-elementowym podzbiorem. Dla danego zbioru
n-elementowego istnieje 2^N - 1 kombinacji (bo zbiór pusty kombinacją
nie jest) o liczebności od 1 do N. W zadaniu chodzi o znalezienie
wszystkich kombinacji zbioru, o długości od 1 do N.

argothiel

(bo zbiór pusty kombinacją
nie jest)


A to dlaczego?

o liczebności od 1 do N. W zadaniu chodzi o znalezienie
wszystkich kombinacji zbioru, o długości od 1 do N.


Cóż, to już może rozstrzygnąć autor zadania. W obecnej formie upierałbym
się jednak przy długości od 0 do N.

Pozdrawiam, argothiel

podlak

Cóż, to już może rozstrzygnąć autor zadania. W obecnej formie upierałbym
się jednak przy długości od 0 do N.

Pozdrawiam, argothiel


Z matematycznego punktu widzenia 0 też jest jakimś wariantem. Ale z
punktu widzenia mojego problemu zbiór pusty nie ma sensu.

chodzi) to raczej nie do przejścia :)

pozdrawiam
M

Łukasz 'Maly' Ostrowski

| Cóż, to już może rozstrzygnąć autor zadania. W obecnej formie
| upierałbym się jednak przy długości od 0 do N.
Z matematycznego punktu widzenia 0 też jest jakimś wariantem. Ale z
punktu widzenia mojego problemu zbiór pusty nie ma sensu.


Na pierwszy rzut oka chodzi o jakiś program do łamiania haseł ;).
A hasło puste jest dość popularne imo ;).
argothiel

Na pierwszy rzut oka chodzi o jakiś program do łamiania haseł ;).
A hasło puste jest dość popularne imo ;).



zbioru liczb takie, aby dawały konkretną sumę. Jeśli ta suma <0, to
faktycznie kombinacje po 0 nie mają sensu :)

Pozdrawiam, argothiel

Doodge


| Na pierwszy rzut oka chodzi o jakiś program do łamiania haseł ;).
| A hasło puste jest dość popularne imo ;).

zbioru liczb takie, aby dawały konkretną sumę. Jeśli ta suma <0, to
faktycznie kombinacje po 0 nie mają sensu :)


Jesli tak, to trzeba to troszke sprytniej zrobic i wtedy uniknie sie 2^40
zamieniajac to na 2^20, co juz jest o wiele bardziej znosne ;-)
podlak

Na pierwszy rzut oka chodzi o jakiś program do łamiania haseł ;).
A hasło puste jest dość popularne imo ;).


programik nie ma nic wspolnego z lamaniem jakichkolwiek hasel. Chodzi
mi o problem, ktory przedstawialem w jednycm z poprzednich postow. Mam

ktory znadzie wszyskie mozliwe kombinacje tych liczb, ktore dadza 0.
Czyli np. 200, 300, -500. Tylko, ze to wychodzi ogromna liczba
kombinacji.

Łukasz 'Maly' Ostrowski

programik nie ma nic wspolnego z lamaniem jakichkolwiek hasel. Chodzi
mi o problem, ktory przedstawialem w jednycm z poprzednich postow. Mam

ktory znadzie wszyskie mozliwe kombinacje tych liczb, ktore dadza 0.
Czyli np. 200, 300, -500. Tylko, ze to wychodzi ogromna liczba
kombinacji.


Problem plecakowy, NP-zupełny z tego co kojarze. Dla tegoż relatywnie
dobrze działa algorytm zachłanny[google.pl - algorytm zachłanny,
greedy algorithm, problem plecakowy, problem NP-zupełny]. Jeżeli chcesz
to wyznaczyć jednoznacznie to niestety w tym wypadku masz złożoność
rzędu O(2^n) przy n=2*40. W razie problemów wróć na grupe -
podyskutujemy ;).
argothiel

Mam

ktory znadzie wszyskie mozliwe kombinacje tych liczb, ktore dadza 0.


Czyli jednak kombinacje "po zero" również powinieneś brać pod uwagę.
Zero elementów daje sumę zero (chyba że się mylę :)).

Pozdrawiam, argothiel

gobo...@o2.pl

programik nie ma nic wspolnego z lamaniem jakichkolwiek hasel. Chodzi
mi o problem, ktory przedstawialem w jednycm z poprzednich postow. Mam

ktory znadzie wszyskie mozliwe kombinacje tych liczb, ktore dadza 0.
Czyli np. 200, 300, -500. Tylko, ze to wychodzi ogromna liczba
kombinacji.


Masz jakiekolwiek ograniczenia nałozone na wielkość tych liczb? Bo
jeżeli są powiedzmy z przedziału <-10^6,10^6 to nie ma żadnego
problemu, max kilka sek i będzie rozwiązanie. Problem jest jeżeli
nie masz żadnych ograniczeń :/

podlak

Masz jakiekolwiek ograniczenia nałozone na wielkość tych liczb? Bo
jeżeli są powiedzmy z przedziału <-10^6,10^6 to nie ma żadnego
problemu, max kilka sek i będzie rozwiązanie. Problem jest jeżeli
nie masz żadnych ograniczeń :/


No właśnie, problem polega na tym, że zakres liczb poznaje dopiero
po zaimportowaniu ich d programu. Nie ma ograniczen, chociaz w praktyce
jest to okolo max.  <-10^9,10^9. I to jest też problem.

podlak

Problem plecakowy, NP-zupełny z tego co kojarze. Dla tegoż relatywnie
dobrze działa algorytm zachłanny[google.pl - algorytm zachłanny,
greedy algorithm, problem plecakowy, problem NP-zupełny]. Jeżeli chcesz
to wyznaczyć jednoznacznie to niestety w tym wypadku masz złożoność
rzędu O(2^n) przy n=2*40. W razie problemów wróć na grupe -
podyskutujemy ;).


Tylko z tego co analizowalem problem plecakowy, to mamy w nim do
czynienia z ograniczeniem w poztaci objetosci plecaka. Tutaj nie ma
takiego ograniczenia, bo rozwiazaniem moga byc nawet wszystkie liczby.

podlak

Czyli jednak kombinacje "po zero" również powinieneś brać pod uwagę.
Zero elementów daje sumę zero (chyba że się mylę :)).


Zero to tez wynik, ale nie ma sensu w tym zadaniu. Musza byc co
najmniej 2 liczby, a zadna nie jest zerem.

Łukasz 'Maly' Ostrowski

Tylko z tego co analizowalem problem plecakowy, to mamy w nim do
czynienia z ograniczeniem w poztaci objetosci plecaka. Tutaj nie ma
takiego ograniczenia, bo rozwiazaniem moga byc nawet wszystkie liczby.


Tak ale zauważ że to jest powiedzmy zmodyfikowany problem plecakowy
[pojemnościa plecaka jest zero - chcesz upchać ileś tam przedmiotów
z czego część z nich jest "czarnymi dziurami" ;)],
wybierasz tak "zachłannie" kolejne liczby żeby być jak najbliżej zera,
a rozpocząć od powiedzmy losowej/największej/najmniejszej liczby.

Zakładając że mamy:

1 3 6 4
-2 -6 -7 -8

Zacznijmy sobie od 1,
x = {1} \sum{x} = 1
Najlepiej wziąść -2, bo zbliżamy sie najbardziej do zera:
x = {1, -2} \sum{x} = -1
teraz weżmy 3
x = {1, -2, 3} \sum = 2
weźmy se teraz powiedzmy -6
x = {1, -2, 3, -6} \sum = -4
a teraz ostatecznie wybieramy 4
x = {1, -2, 3, -6, 4} \sum = 0.

;). Niewiem czy rozumiesz idee, raczej powinieneś.

A co do formalnego sposobu, tak jak na którejś grupie już Ci
odpowiedziano - zauważ że wystarczy że zrobisz liczbe
80-bitową[40 + 40] - i będziesz ją zwiększał o 1 - kolejne
jej bity będą odpowiadały występowaniu odpowiednich liczb.

Czyli formalnie np:
X = {1 2 -3}
i = 0,   ib = {0, 0, 0} czyli wynikowo zbiór pusty {} - odpada
++i = 1, ib = {0, 0, 1} czyli {-3} - suma -3
++i = 2, ib = {0, 1, 0} czyli {2} - suma 2
etc
++i = 3, ib = {0, 1, 1} czyli {2, -3} - suma -1
etc
++i = 7, ib = {1, 1, 1} czyli {1, 2, -3} - suma 0 - pasuje.

Musisz tylko "ręcznie" zaimplementować przeniesienie - bo liczby
intowej 80-bitowej brak afaik ;). Kończysz inkrementacje
jak nastąpi overflow. ;)

Gobol

Zakładając że mamy:

1 3 6 4
-2 -6 -7 -8

Zacznijmy sobie od 1,
x = {1} \sum{x} = 1
Najlepiej wziąść -2, bo zbliżamy sie najbardziej do zera:
x = {1, -2} \sum{x} = -1
teraz weżmy 3
x = {1, -2, 3} \sum = 2
weźmy se teraz powiedzmy -6
x = {1, -2, 3, -6} \sum = -4
a teraz ostatecznie wybieramy 4
x = {1, -2, 3, -6, 4} \sum = 0.

;). Niewiem czy rozumiesz idee, raczej powinieneś.

A co do formalnego sposobu, tak jak na którejś grupie już Ci
odpowiedziano - zauważ że wystarczy że zrobisz liczbe
80-bitową[40 + 40] - i będziesz ją zwiększał o 1 - kolejne
jej bity będą odpowiadały występowaniu odpowiednich liczb.

Czyli formalnie np:
X = {1 2 -3}
i = 0,   ib = {0, 0, 0} czyli wynikowo zbiór pusty {} - odpada
++i = 1, ib = {0, 0, 1} czyli {-3} - suma -3
++i = 2, ib = {0, 1, 0} czyli {2} - suma 2
etc
++i = 3, ib = {0, 1, 1} czyli {2, -3} - suma -1
etc
++i = 7, ib = {1, 1, 1} czyli {1, 2, -3} - suma 0 - pasuje.

Musisz tylko "ręcznie" zaimplementować przeniesienie - bo liczby
intowej 80-bitowej brak afaik ;). Kończysz inkrementacje
jak nastąpi overflow. ;)

--
Pozdrawiam,
Łukasz 'Maly' Ostrowski.


Takie obliczanie to by 'troszeczke' zajeło 2^80=1 208 925 819 614 629
174 706 176 a więc podejrzewam że komputer domowy się prędzej spali
niż to obliczy :). Jeżeli już brutforce to można się pobawić
troche inaczej, tylko że to też nie będzie szybkie rozwiązanie a
dodatkowo bęzdie miało ogromną złożoność pamięciową. Robisz
dwa razy plecaczek , raz dla dodatnich raz dla ujemnych, wyniki masz w
dwóch tablicach. Sortujesz obie i wyszukujesz czy są te same
wartości w obu.
A co do pierwszego algorytmu to on nie działa, tzn działa tylko
czasami i nie zwraca wszystkich rozwiązań

Łukasz 'Maly' Ostrowski

Takie obliczanie to by 'troszeczke' zajeło 2^80=1 208 925 819 614 629
174 706 176 a więc podejrzewam że komputer domowy się prędzej spali
niż to obliczy :).



NP-trudny/zupełny(zawsze myle te pojęcia ;)). [btw. a nóż trafi
na rozwiązanie w pierwszych 5 iteracjach ;)].

<ciach
A co do pierwszego algorytmu to on nie działa, tzn działa tylko
czasami i nie zwraca wszystkich rozwiązań


Ale jest relatywnie szybki jeżeli już ma w zapisane w losie że
trafi na rozwiązanie - dlatego zasugerowałem zaczynanie od
elementu losowego/największego/najmniejszego.

Gobol
Można by to w sumie zrobić w mniej niż 10^11 operacji ale potrzebne
by było od cholery pamięci i to jest główną przeszkodą :/ Wydaje
mi sie że może istnieć rozwiązanie, gdyż na opss jest podobne
zadanie i tam jest 500 liczb, wprawdzie z przedziału <-500;500i da
się spokojnie sprawdzić czy można z nich uzyskać dowolną sumę S w
czasie 0.01s, ale nie wiem jak to zrobić przy niskiej złożoności
pamięciowej a są rozwiązania gdzie wymagane jest tylko 260KB, może
dało by sie to jakoś przełożyć.
Andrzej Grażyński


| Na pierwszy rzut oka chodzi o jakiś program do łamiania haseł ;).
| A hasło puste jest dość popularne imo ;).

programik nie ma nic wspolnego z lamaniem jakichkolwiek hasel. Chodzi
mi o problem, ktory przedstawialem w jednycm z poprzednich postow. Mam

ktory znadzie wszyskie mozliwe kombinacje tych liczb, ktore dadza 0.
Czyli np. 200, 300, -500. Tylko, ze to wychodzi ogromna liczba
kombinacji.


Jest takie hasło "Algorytm nawrotu". Poczytaj sobie i zastosuj.

podlak

Jest takie hasło "Algorytm nawrotu". Poczytaj sobie i zastosuj.


Algorytm nawrotu nie służy przypadkiem do wyznaczania permutacji? Bo
ten problem nie jest permutacją. Liczba elementów moze być dowolna
od 2 do n.

Andrzej Grażyński


| Jest takie hasło "Algorytm nawrotu". Poczytaj sobie i zastosuj.

Algorytm nawrotu nie służy przypadkiem do wyznaczania permutacji? Bo
ten problem nie jest permutacją. Liczba elementów moze być dowolna
od 2 do n.


Kombinacje x elementowe z y elementoów.
Dziekuje wszystkim + nowy problem
Wyswietlanie wszystkich linii pliku
do wszystkich co mnie lubia
  • pl prawo
  • gg;na;se;k500i
  • cykl bezowulacyjny a bol piersi
  • druki ft 0100
  • scypion afrykanski mlodszy
  • Skupisko tematów z for dyskusyjnych : Start