Van egy olyan problémám, hogy adott n elem, amit m csoportba kell rendezni. Az alappélda egyszerű, adott 6 elem, amit két egyforma elemszámú csoportba kell rendezni. A kérdés, hányféleképpen tudom ezt megtenni? Emlékeim szerint ez a kérdéskör a kombinatorika témakörbe tartozik. Utoljára pont húsz éve tanultam kombinatorikát, szóval megkoptak az emlékeim.
Kérdésem, mi a pontos témakör, van erre valami ismert algoritmus amit használni lehet kevésbé egyszerű esetben (pl 10 elem, két nem feltétlen egyenlő elemszámú csoportba, de a csoportok elemszáma minimum 3; 100 elem, egyenlő elemszámú, de akárhány csoportba, stb)?
Szóval pointereket kérnék, merre olvasgassak utána (wikipédia is jöhet, abban is elvesztem).
Köszönöm,
Csaba
- 3482 megtekintés
Hozzászólások
Alapvetően az n!-t kell oszatni mindenfélével. Nevezetesen a csoportok elemszámának faktoriálisával, pl: 6! / (3! * 3!)
> pl 10 elem, két nem feltétlen egyenlő elemszámú csoportba,
ha az első csoport elemszáma k, akkor:
10! / (k! * (10-k)!) -- ezt úgy is mondják, hogy "10 alatta a k"
> de a csoportok elemszáma minimum 3;
ennek nincs jelentősége
> 100 elem, egyenlő elemszámú, de akárhány csoportba, stb)?
ha m csoport van:
100! / ((100/m)!)^m -- mondjuk itt m legyen 1,2,4,5,10,20,25,50,100
- A hozzászóláshoz be kell jelentkezni
Köszönöm neked is a választ.
--
Csaba
- A hozzászóláshoz be kell jelentkezni
"Alapvetően az n!-t kell oszatni mindenfélével. Nevezetesen a csoportok elemszámának faktoriálisával, pl: 6! / (3! * 3!)"
Picit pontosítanék. A fenti abban az esetben igaz, ha a két csoportot megkülönböztetjük. Azaz az {a,b,c} az egyik és { d,e,f} a másik, illetve {d,e,f} az egyik és {a,b,c} a másik más esetnek számít. Különben a fentit osztani kell 2-vel
- A hozzászóláshoz be kell jelentkezni
Amennyiben az is számít, hogy melyik csoportba kerülnek az elemek, nem kell osztani 2-vel, mert pl. úgy elképzelve, hogy sorban van a 6 elemed, és felé írsz 1-eseket és 2-eseket (3-3 db-ot), hogy 1-es, vagy 2-es csoport (azaz megcimkézed a csoportosítandó elemeket a csoportcimkékkel). Így a kérdés az lett, hogy hányféleképpen rendezhetsz sorba 6 elemet, úgy, hogy van köztük 3-3 egyforma (1, 1, 1, 2, 2, 2), azaz a csoportcimkék sorrendjeinek a számát határozod meg. És így bizony az 1, 1, 1 Az meg 6!/(3!*3!). Vagy álatlánosan n!/(k1!*k2!*...kr!) (n elem, r csoport és k1, k2, ..., kr csoportelemszámok esetén).
Ha nem számít, akkor kell osztani. De ez csak egyenlő elemszám esetén releváns. Általános esetben több egyenlő elemszámú csoport esetén az egyenlő elemszámú csoportok faktoriálisával kell osztani még.
De valaki javítson ki, ha nem jól gondoltam át hirtelen.
- A hozzászóláshoz be kell jelentkezni
Az ismétlés nélküli kombináció a barátod. Alapesetben n alatt k (n!/[(n-k)!k!]) az általános képlet. Ahol n az elemek száma, és k elemet akarsz kiválasztani. Viszont ahány esetet felsoroltál, annyi megoldás lesz.
Pl.:
- n elem két csoportba, és az első csoportba k elem: (n alatt k) módon válogathatod össze az első csoportot. A maradék lesz a második csoport, amit már csak egyféleképpen rakhatsz ki.
- n elem több csoportba osztása, csoportonként k1, k2,..., ki elemmel: (n alatt k1)*(n-k1 alatt k2)*…*(n-k1-…-ki-1 alatt ki) Ha van még maradék a ki kiválogatása után, akkor azt már csak egy csoportba teheted.
- A hozzászóláshoz be kell jelentkezni
Köszönöm, ez nagyon hasznos volt. Ez alapján megtaláltam a DescTools R library-t, ami nem csak a kombinációk számát adja meg, de magukat a kombinációkat is legenerálja nekem. Ráadásul figyelembe tudja venni a speciális feltételeimet is (pl változó elemszámú csoportok), szóval pontosan ez kell nekem az adott projekthez.
--
Csaba
- A hozzászóláshoz be kell jelentkezni
OFF
A párom nagyon jól tud kombinálni, szerintem megkérdezem, hogy mit gondol erről az egészről
- A hozzászóláshoz be kell jelentkezni
Hja kérem, egy ilyen kvantumszámítógép nem piskóta, bármit kiértékel bármi mással, tér- és idődimenziókon átugorva, csak értelmezni kell az eredményt. Sajnos, arra jellemzően csak egy másik, hasonló kvantumszámítógép képes - de nem mindegyik, sőt a legtöbb teljesen inkompatibilis egymással.
- A hozzászóláshoz be kell jelentkezni
Pont az eredmény értelmezéssel van gond. Egy nőnél a nem igent, az igen nemet jelent, de nem mindig!
- A hozzászóláshoz be kell jelentkezni
Kicsit bonyolultabb ennél. Nem=igen, igen=talán, talán=nem, de nem mindig.
- A hozzászóláshoz be kell jelentkezni
Kicsit kevered, a diplomatánál az 'igen' jelentése 'talán', a 'talán' jelentése 'nem'; ha 'nem'-et mondana, akkor nem is lenne diplomata.
Egy úrinőnénél a 'nem' jelentése 'talán', a 'talán' jelentése 'igen'; ha 'igen'-t mondana, akkor nem is lenne úrinő.
- A hozzászóláshoz be kell jelentkezni
Bárcsak ennyire egyszerű lenne :D
- A hozzászóláshoz be kell jelentkezni
Ha meg is kell jeleníteni, akkor Ruby-ban elég egyszerű:
[1,2,3,4].combination(2).to_a
vagy ha épp permutáció is kell:
[1,2,3,4].permutation.to_a
- A hozzászóláshoz be kell jelentkezni