Kombinációk generálása

Algoritmusok

Üdv!

Egy saját projectnél merült fel a következő problémám: Hasonló a probléma mint a lottónál. Van mondjuk, a példa kedvéért 90 szám amiből ugye 5-öt kell kiválasztani, ismétlés nélkül. Tehát az 1,2,3,4,5 ugyan az mint az 1,2,4,5,3. Szóval ezen összes lehetőséget szeretném legeneráltatni egy scripttel, de nem tudok rá pontos algoritmust megfogalmazni. Ebben szeretnék segítséget kérni. Tehát egy olyan algoritmusra van szükségem, ami egy adott számtartományból(pl. 1-90) legenerálja az összes lehetséges x számból álló kombinációt, és utána ezek közül meg tudjam határozni pl az összes olyan kombinációt ami "kéttalálatos" a lottón. Tehát az összes olyan 5 hosszú kombináció kellene, amiben benne van az 1-90-ig számokból előállítható számpár. Bocsánat a kesze-kusza magyarázásért, nem tudom ettől jobban szavakba önteni. A problémára azt hiszem a lottó a legjobb hasonlat.

Köszi, karika200

  • 9926 megtekintés

( mulder | 2010. 09. 16., cs – 16:17 )

legyen az 5 szamod: a,b,c,d,e

a 1-86-ig
b a+1-tol 87-ig
c b+1-tol 88-ig
d c+1-tol 89-ig
e d+1-tol 90-ig

ugyanis ilyenkor a kisebb b kisebb c kisebb d kisebb e mindig teljesul.

Legalabbis ha jol gondolom :)

Hmm, az a baj, hogy rosszul írtam a topikban, bocsánat. Szóval, amit szeretnék, hogy a 90 számból az összes 5 számjegyű kombináció a módszerrel valóban előállítható, de szeretném kiválogatni belőle, azt a 4005 darabot, ami az összes 90 számból kiválasztott 5 hosszú kombinációk közül az összes "kéttalálatos" lottószám lenne. bocsánat még egyszer. :)

Ha pl 90 szambol kell a ketteseket generalni (a ket talalat: 25, 59), akkor az elobbi ciklus felveszi az
(a,b)=(25, 59), c,d,e szabadonfuto, de az elobbi megkotesekkel (b kisebb c, c kisebb d, etc)
majd
(a,c)=(25, 59)
(a,d)=(25,59)
(a,e)=(25,59)

majd
(b,c)=(25,59)
...
(d,e)=(25,59)

Igy?

Igen, de a lehető legkevesebb kombinációra van szükségem. Ez a verzió pedig többet ad, mint kellene szerintem.

pl.:

1,2,3,4,5
1,2,3,4,6

Itt is az 1,2 a 2,3 a 3,4 a 4,1 és a 3,1 számpárok mind 2 esetben kirakhatók. Tehát a feladat bonyolultságát az adja, hogy egy 5 hosszú kombinációból 10 2-es számpár is kijön, és úgy kellene ezeket előállítani, hogy ami számpárt már kiraktunk, az többet ne forduljon elő.

( hnsz2002 v | 2010. 09. 16., cs – 16:39 )

Halmazként kezeld mindkettőt, az 1-90ig számokat és a kihúzottakat is. Így biztos nem veszed ki kétszer ugyanazt, és mivel halmaz, sorrend sincs a kihúzott elemek között.
--
Discover It - Have a lot of fun!

+1

dobsz egy egesz x veletlen egesz szamot 0 <= x < 43949268 = (90;5) tartomanyban, majd ehhez hozzarendeled az x-ik szam-o"to"st. hogy ha x < (89;4), akkor az elso" sza'm az 1-es, ha (89;4) <= x < (89;4)+(88;4), akkor a 2, stbstb. a maradek szamnegyesbol pedig hasonlokeppen tudod levalogatni a szamokat, lenyegeben egy egyszeru" ciklussal.

A.

( Jason v | 2010. 09. 20., h – 22:22 )

Ha jól értem, az ötöslottó halmazán akarod legenerálni az összes, bizonyos feltételnek megfelelő tuple-t (vagymi)?

Ugye az összes variáció 90*89*88*87*86, azaz 90!/85!.
Ha ebből kettő ismert, akkor marad 88*87*86, azaz 88!/85!.
Ha 3, akkor 87*86 kombináció van értékötösökre.

--
"SzAM-7 -es, tudjátok amivel a Mirage-okat szokták lelőni" - Robi.

( log69 | 2010. 09. 21., k – 08:11 )

"Van mondjuk, a példa kedvéért 90 szám amiből ugye 5-öt kell kiválasztani, ismétlés nélkül. Tehát az 1,2,3,4,5 ugyan az mint az 1,2,4,5,3. Szóval ezen összes lehetőséget szeretném legeneráltatni egy scripttel..."

Erre a kérdésedre összedobtam hamar gyorsan egy python script-et, optimalizálások nélkül az olvashatóság jegyében:
http://pastebin.com/knecuSdj 


#!/usr/bin/python
# coding=utf8

# PRINT COMBINATIONS OF X FROM N
# written by Andras Horvath <han at log69.com> (2010) Public Domain

n = 6
x = 3

if (x > n): n, x = x, n

a = range (1, x+1)

while (1):

   print a

   if (a[x-1] == n):
            lim = 0
            for i in range (x, 0, -1):
               if (a[i-1] < n-(x-i)):
                  lim = i
                  break
            if (lim == 0): exit ()
            a[lim-1] += 1
            for i in range (lim+1, x+1):
               a[i-1] = a[i-2] + 1
   else:
      a[x-1] += 1

egyébként szemléletesen fogalmazva, a lista bal oldalán felsorakoztatjuk a számokat, majd a log jobb oldalit szépen végig sétáltatjuk a végéig, ekkor jobbról a következőt is léptetjük egyell jobbra, a végén lévő meg visszaugrik és besétálja a fennmaradó, immáron eggyel kisebb részt.

kb.: 


123...
12.4..
12..5.
12...6
1.34..
1.3.5.
1.3..6

1..4.6
1...56
.234..

stb.

szerk.: na tegnap nekem is késő volt már nagyon, most javítottam az algoritmust, és tesztelve :)

( szemet | 2010. 09. 20., h – 23:29 )

(szerk: a következő kommentem érint, de bent hagyom ezt, hátha valaki érdekesnek találja ezt is:)

Ez a "lottery problem" amire gondolhatsz.

Nagyon-nagyon bonyolult és nincs általános megoldása.

Speciális eset (nem konstruktív bizonyítással), ahhoz hogy biztos legyen kettesed, az pl. 100 szelvénnyel megoldható a magyar lottón:

http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_lotto.pdf

szerk: Bocs a te problémád egyszerűbb. Te nem azt akarod hogy a kihúzott 5 szám közül legyen olyan kettes amivel nyersz, egyszerűen csak az összes kettest le akarod fedni, ugye?

( szemet | 2010. 09. 20., h – 23:12 )

Na jó mégsem egyszerű.
A te problémád az NP-teljes Set-cover probléma! ;)
http://en.wikipedia.org/wiki/Set_cover_problem

Vannak alaphalmazaid: az összes létező ötös kombináció
Ezt célszerűen számpárok halmazaiként képzelheted el, így pl. : 1 2 3 4 5 ->
1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5

Szóval van ez a binom(90,5) darab számpár halmazod és a minimális számút akarod kiválasztani ami az összes számpárt lefedi.

NA pont EZ a set-cover probléma! Szóval heurisztikában gondolkodj... Remélem segítettem. :P

Esetleg némi reményt ad, hogy speciális és szimmetrikus a probléma az általános set-coverhez képest, de ehhez már sokat kéne gondolkodnom: és most már késő van... ;)

De azt el tudom képzelni hogy a mohó stratégia itt jobb eredményt ad mint az általános problémára.

mohó strat.: mindig egy olyan ötöst választasz be az eredményhalmazba ami a legtöbb még nem lefedett számpárt tartalmazza...