Fórumok
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
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
Köszönöm neked is a választ.
--
Csaba
"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
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.
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.
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
OFF
A párom nagyon jól tud kombinálni, szerintem megkérdezem, hogy mit gondol erről az egészről
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.
https://youtu.be/0BxckAMaTDc?t=114
Pont az eredmény értelmezéssel van gond. Egy nőnél a nem igent, az igen nemet jelent, de nem mindig!
Kicsit bonyolultabb ennél. Nem=igen, igen=talán, talán=nem, de nem mindig.
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ő.
Bárcsak ennyire egyszerű lenne :D
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