Diskuze: Seznam permutací a jeho vykrácení

Petr Vavřinec

Člen

Petr Vavřinec:13.2.2020 0:49

Ahoj. Potřeboval bych nakopnout správným směrem. Pomocí modulu itertools si vygeneruju pětičlenné permutace (z prvků ABCDE), takže mám seznam pětic (ABCDE, ABCED, ABDCE, ABECD atd.). Celkem je jich 120, protože 5! je 120. Teď to vykrátím, protože potřebuji jen ty permutace, které po otočení (reverzi pořadí) ještě v seznamu nejsou. Například ABCDE je pro mne shodná s EDCBA, protože jsou k sobě reverzní, rovněž CEDAB je pro mne shodná s BADEC, protože jsou k sobě reverzní, atd. Čili mi vznikne 60 permutací, protože logicky každá permutace z původního seznamu má k sobě jednu reverzní permutaci. Tohle bych zvládnul.
Jenže já bych potřeboval vybrat nejenom permutace, které vyhovují výše uvedenému pravidlu, ale současně aby to byly ty permutace, u kterých, když spočtu výskyty jednotlivých prvků na jednotlivých pozicích, tak aby v celém seznamu byl rovný výskyt všech prvků a navíc na všech pozicích.
Čili kdybych sčítal výskyty pro příklad jen z těchto permutací ABCDE, ABCED, ABDCE, ABECD, vyšlo by mi, že A na první pozici je 4x a nikde jinde, B na druhé pozici je 4x a nikde jinde, ale C je na třetí pozici 2x a na čtvrté pozici 2x, D je na třetí pozici 1x, na čtvrté 1x, na páté 2x, E je na třetí pozici 1x, na čtvrté 1x a na páté pozici 2x. V celém seznamu jsou tedy všechna písmena zastoupena stejněkrát (logicky, jsou to permutace různých prvků), ale na jednotlivých pozicích nejsou zastoupeny rovnoměrně (resp. v celém vykráceném seznamu schodně).
Kdybych vzal totiž z původní čtveřice ABCDE, ABCED, ABDCE, ABECD místo poslední pětice její reverzní pětici DCEBA, takže bych měl ABCDE, ABCED, ABDCE, DCEBA, rozložení na pozicích se změní, vylepší v můj prospěch, protože bych měl A na první pozici 3x a zároveň by se objevilo na poslední pozici poprvé, čímž se blížím k víc vyváženému stavu na jednotlivých pozicích, než v tom prvním případě.
Vím, z nějakého ručního ladění v Excelu, že existuje způsob, jak v seznamu zbyde oněch 60 permutací, kdy každý prvek je zastoupen na každé pozici právě 12x, čili přesně to, co potřebuji. Ale to jsem udělal metodou ruční a vizuální. Jak to provést kódem, na to mi myšlenka nechce přijít.
Napadá mně jedině nějaké rekurentní řešení, kdy sestavím ten vykrácený seznam stejně jako v kódu níže, ale po cestě sčítám ty četnosti prvků na pozicích. Ve chvíli, kdy bych měl zařadit pětici, díky které bych přetekl někde tu četnost 12ti výskytů na pozici, vrátil bych se zpátky a vzal její reverzní podobu... A tak dále. Ale asi existuje jiný způsob. U toho mnou nabízeného asi neumím ošetřit to zpětné odrolování spočtených výskytů.

Zkusil jsem:

import itertools as it
from collections import Counter as ct # tohle by mi možná mohlo pomoci při tom sčítání na pozicích
b=list(it.permutations("ABCDE",5)) # vygeneruj všechny pětičlenné permutace
c=[]                                                  # připrav si další seznam na uložení jen těch vyhovujících
for i in b:                                          # projdi všechny permutace
    a=tuple(reversed(i))                    # zjisti jejich reverzní podobu
    if a not in c and i not in c:            # pokud není v novém seznamu ani aktuální pětice, ani její revezní podoba
        c.append(i)                              # přidej do seznamu aktuální pětici, ale zrovna tak by šlo přidat místo ní tu reverzní, pokud by mi to pomohlo k tomu konečnému vyváženému stavu, ale nevím, jak se rozhodnout, jestli vložit aktuální nebo tu reverzní

print("Počet vykrácených: ",len(c),"\n",c)
print("Počet všech: ",len(b),"\n",b)

Chci docílit: Tvořím stolní hru, kde jsou karty se vzorovými pěticemi, které se hráč snaží posunováním barevných kamenů vytvořit na herním plánu. Ale je jedno, jestli si hráč dá kartu do ruky "hlavou vzhůru" či "nohama vzhůru", proto krátím ty reverzní pětice. Ale chci, aby každá barva měla na každé pozici stejnou četnost zastoupení.

Děkuji za každý nápad, jak to vyřešit programově a nikoli ručně, jak jsem to udělal já v Excelu.

Petr V.

Odpovědět

13.2.2020 0:49

Peter Mlich

Člen

Peter Mlich:14.2.2020 8:14

Zkus popsat, jak jsi to udelal v excelu.
Prilis nechapu, jak to presne funguje. Jake kombinace jsou pripustne a jake uz ne a proc. Sice to popisujes, ale asi je moc brzo po ranu
Prvne jsem myslel, ze popisujes neco takovehoto, ale pak mne to uplne zmatlo...

Vytvor kombinace pro ABCDE
Vyber z nich takove, aby se neopakoval retezec ABCDE a EDCBA (pozpatku) a to pro vsechny uz vybrane kombinace.
A soucasne, aby se neopakoval ten retezec pri posunu znaku, cili ABCDE BCDEA, cili, retezec je rotaci kombinace

Cili, bys musel pro kazdou ulozenou kombinaci vytvorit vsechny jeji rotace a totez pozpatku a ulozit do pole, se kterym porovnavas novou kombinaci, zda je povolena.
Mno, ale pak si to zkomplikoval necim dalsim, kde uz vubec nerozumim, proc. A asi to vubec neopodvida memu popisu

Priklad k tomu memu popisu:

ABCDE
| ABCDE, BCDE-A, CDE-AB, DE-ABC, E-ABCD - ulozim vsechny rotace pro abcde
| EDCBA, DCBA-E, CBA-ED, BA-EDC, A-EDCB - ulozim rotace pro opacne poradi edcba

Pridam dalsi kombinaci, ktera neni v tabulce ulozenych a pridam do tabulky opet vsechny moznosti, ktere nesmi mit zadna dalsi pridana.
Cili, pokud rikas, ze je puvodne 120, tak ve vysledku by mohlo byt odhadem 120/10=+-12 kombinaci.

A nemuzes treba spis popsat, jakym zpusobem by hra mela presne fungovat a proc by tam meli byt prave tve kombinace?

Editováno 14.2.2020 8:15

Nahoru Odpovědět

14.2.2020 8:14

Petr Vavřinec

Člen

Petr Vavřinec:14.2.2020 15:09

Ahoj Peter.
Vážím si toho, jak se tady snažíš pomoct všem. Ano, vím, že to neumím dobře popsat. Jen se zeptám, ty si můžeš spustit Python kód? Protože vím, že asi předně používáš PHP!?!?

Máš pravdu v té první části, kdy ze seznamu vyškrtám ty pětice, které jsou tam už obsaženy v obráceném pořadí. Jsou to permutace, čili n-tice ze všech n prvků, které se střídají na všech pozicích. Logicky tedy každá permutace (např. ABCDE) má v kompletním seznamu i svou reverzní permutaci (čili EDCBA). Pro mně je ABCDE a EDCBA jedno a totéž, protože hráč si může otočit kartu v ruce o 180 stupňů a tím pádem vidí tu reverzní permutaci. A já nechci, aby mohl do ruky dostat dvě karty, které mají na sobě stejnou permutaci (i po otočení karty), proto vykrátím ty reverzní. To ten můj kód dělá dobře. Ze 120ti původních permutací jich zbyde 60.

S tou rotací si to nepochopil (ale ten problém řeším taky, ale v jiné části té hry, takže určitě nějak budu řešit zrotované pětice, ale dnes a tady ne).

Jde mi teď o to, že potřebuji, aby na první pozici v těch 60ti pěticích se objevilo 12xA, 12xB, 12xC, 12xD a 12xE. Zrovna tak na druhé pozici, na třetí, na čtvrté i na páté. Momentálně, když spustím tenhle kód:

import itertools as it
import random as rnd
from collections import Counter as ct # tohle by mi možná mohlo pomoci při tom sčítání na pozicích
b=list(it.permutations("ABCDE",5)) # vygeneruj všechny pětičlenné permutace
c=[]                                                  # připrav si další seznam na uložení jen těch vyhovujících
for i in b:                                          # projdi všechny permutace
    a=tuple(reversed(i))                    # zjisti jejich reverzní podobu
    if a not in c and i not in c:            # pokud není v novém seznamu ani aktuální pětice, ani její revezní podoba
        c.append(i) if rnd.choice([True, False]) else c.append(a)  # je mi víceméně jedno, jestli vložím aktuální nebo reverzní pětici                           # přidej do seznamu aktuální pětici, ale zrovna tak by šlo přidat místo ní tu reverzní, pokud by mi to pomohlo k tomu konečnému vyváženému stavu, ale nevím, jak se rozhodnout, jestli vložit aktuální nebo tu reverzní

print("Počet vykrácených: ",len(c),"\n",c)
# print("Počet všech: ",len(b),"\n",b)

transc=list(map(list, zip(*c))) # tady převedu tu matici 60 řádků krát 5 sloupců na matici 5 řádků krát 60 sloupců, abych snadno spočítal, kolikrát je tam A nebo B nebo C nebo D nebo E
# print(transc) #tady si můžeš vytisknout tu transponovanou matici
print("Na první pozici se objeví: ",ct(transc[0]))
print("Na druhé pozici se objeví: ",ct(transc[1]))
print("Na třetí pozici se objeví: ",ct(transc[2]))
print("Na čtvrté pozici se objeví: ",ct(transc[3]))

Když si tenhle kód spustíš několikrát, vždycky budeš mít 60 jedinečných pětic, které v seznamu nemají svojí reverzní podobu. Jenže pokaždé ti vyjde jiný počet výskytů prvků A,B,C,D,E v prvním, druhém, třetím, čtvrtém a pátem sloupci. A já tedy potřebuju, aby počet všech prvků v každém sloupci byl přesně 12.

Samozřejmě by se dal celý algoritmus spustit v nekonečném cyklu a vyskočit z něj až když ten počet všech prvků v každém sloupci bude 12. Ale to je metoda prakticky nekonečná.

Na devátém řádku jsem změnil vkládání permutace do výsledného seznamu. Mě je totiž jedno, jestli tam vložím aktuální, nebo reverzní pětici (ale jen jednu z nich!!!), protože je mi jedno, jestli hráč bude držet kartu v ruce nohama vzhůru nebo ne.

Ptal ses, jak jsem to řešil v Excelu ručně. Z výše uvedeného vyplývá, že je jedno, jestli tam vkládám aktuální nebo její reverzní pětici. A to je jediný způsob, jak docílit ručně v Excelu toho stavu, že jsou na všech pozicích a v každém sloupci prvky právě 12x. Prostě jsem otáčel ručně ty pětice na řádku, dokud se mi nepodařilo srovnat ten stav na 12 prvků v každém sloupci.
Když jsem viděl, že mám moc prvků A v prvním sloupci (třeba 17) a moc prvků E v pátém sloupci (třeba 13), tak jsem pětici ABCDE zreverzoval na tom řádku na EDCBA. Tím se mi zmenšil počet prvků A v prvním sloupci na 16 a počet E v pátém sloupci na požadovaných 12. Samozřrjmě se mi ale změnily i počty a prvky na druhé a čtvrté pozici. Na třetí ne, protože kolem té se to všechno otáčí. A tak jsem pokračoval pořád a pořád, až jsem to všechno srovnal. Ale ten svůj myšlenkový pochod s tím porovnáním, čeho je moc a čeho je kde málo a podle toho vybrat,, jakou pětici zreverzovat, to nejsem schopný popsat kódem. :-(

Snad jsem to teď popsal srozumitelně.

Nahoru Odpovědět

14.2.2020 15:09

Naučíme tě pracovat na home-office.

Zjistit více...

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.