Előző - #37 Változáskészítő | Tartalomjegyzék | Következő - #39 Collatz Sequence

38. GYAKORLAT: VÉLETLENSZERŰ KEVERÉS

keverés([1, 2, 3, 4, 5])  →  [3, 1, 4, 5, 2]

A véletlenszerű keverés algoritmusa véletlenszerű sorrendbe állítja a listában szereplő értékeket, például egy pakli kártya keverését. Ez az algoritmus a listában szereplő értékek új permutációját vagy sorrendjét állítja elő. Az algoritmus úgy működik, hogy a lista minden egyes értékét áthurkolja, és véletlenszerűen meghatároz egy új indexet, amellyel felcserélheti azokat. Ennek eredményeként a listában szereplő értékek véletlenszerű sorrendben vannak.

Egy n értékből álló listához n van! („n faktoriális”) lehetséges permutációk. Például egy 10 értékű listában 10 van! vagy 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 vagy 3 628 800 rendelési lehetőség.

Ez a gyakorlat a helyben módosítja a neki átadott listát , ahelyett, hogy új listát hozna létre és visszaküldené. Mivel a listák változtatható objektumok a Pythonban, a paraméteren végzett módosítások valójában az adott paraméter függvényhívásának átadott eredeti objektumot módosítják. Például írja be a következőket az interaktív héjba:

>>> someList = [1, 2, 3]  # Hozzunk létre egy lista objektumot.

>>> def someFunc(someParam):

... someParam[0] = 'kutya'  # Ez megváltoztatja a listát a helyén.

... someParam.append('xyz')  # Ez megváltoztatja a listát a helyén.

...

>>> someList 

[1, 2, 3]

>>> someFunc(someList)  # Adja át a listát argumentumként.

>>> someList  # Vegye figyelembe, hogy a lista objektumot a függvény módosította.

['kutya', 2, 3, 'xyz']

Figyeljük meg, hogy a lista a függvény paraméterének someListargumentumaként kerül átadásra . Ez a függvény módosítja a someParam-ot (ami ugyanarra a lista objektumra utal, amelyre a someList változó is), így ezek a módosítások a függvény visszatérése után is megmaradnak. A függvény nem ad vissza új listát a lecserélésre ; helyben módosul .someParamsomeFunc()someFunc()someListsomeList

A Pythonban csak a módosítható objektumok (például listák, szótárak és halmazok) módosíthatók helyben. A megváltoztathatatlan objektumok (például karakterláncok, egész számok, sorok és rögzített halmazok) nem módosíthatók helyben.

Gyakorlat leírása

Írjon egy shuffle()függvényt egy értékek paraméterrel egy értéklistába. A függvény nem ad vissza semmit, hanem a lista minden értékét véletlenszerű indexre állítja be. Az eredményül kapott kevert listának ugyanazokat az értékeket kell tartalmaznia, mint korábban, de véletlenszerű sorrendben.

Ez a gyakorlat a Python függvényével azonos függvény megvalósítását kéri random.shuffle(). Ezért ne használja ezt a funkciót a megoldásban, mert ez megsértené a gyakorlat célját.

Ezek a Python- assertutasítások leállítják a programot, ha feltételük False. Másolja őket a megoldási program aljára. Az Ön megoldása akkor helyes, ha a következő assertállítások feltételei mind igazak :

random.seed(42)

# Végezze el ezt a tesztet tízszer:

i tartományban (10):

    testData1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

    keverés(tesztadat1)

    # Győződjön meg arról, hogy az értékek száma nem változott:

    assert len(testData1) == 10

    # Győződjön meg arról, hogy a sorrend megváltozott:

    assert testData1 != [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

    # Győződjön meg arról, hogy az újrarendezéskor minden eredeti érték megvan:

    assert sorted(testData1) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

# Győződjön meg arról, hogy a megkevert üres lista üres marad:

testData2 = []

keverés(tesztadat2)

assert testData2 == []

Próbáljon megoldást írni a leírásban szereplő információk alapján. Ha továbbra is problémái vannak ennek a gyakorlatnak a megoldásával, további tippekért olvassa el a Megoldástervezés és a Különleges esetek és Gotchák című részt.

Előfeltétel fogalmak: import utasítások, randommodul, randint(), forciklusok, range(), len() , értékek felcserélése

Megoldás tervezése

A megoldás meglepően egyszerű. A for ciklus a listában minden indexet át tud hajtani. Minden iterációnál a ciklusban lévő kód kiválaszt egy véletlenszerű indexet. Ezután felcseréli az aktuális iterációs index és a véletlen index értékeit.

Ha a véletlenszerű index megegyezik az aktuális iteráció indexével, ez rendben van: a véletlenszerű keverés tartalmazhat értékeket az eredeti helyükön. Ez valahogy nem „kevésbé véletlenszerű”, mint bármely más permutáció. Ha a véletlenszerű index egy korábban felcserélt index ismétlődése, ez is rendben van. Egy értéket véletlenszerű helyre kétszer keverni nem több vagy kevésbé megkeverni, mint egyszer véletlenszerű helyre mozgatni egy értéket.

Különleges esetek és Gotchák

Ügyeljen arra, hogy shuffle()a függvény ne adjon hozzá vagy távolítson el értékeket a listából; csak a listában már szereplő értékeket szabad átrendeznie. Mivel a shuffle() függvény helyben módosítja az értéklista argumentumot, nem kell semmit visszaadnia. returnA függvényben sehol se legyen utasítás. A Pythonban technikailag minden függvény értéket ad vissza; csak az utasítás nélküli függvények returnaz értéket adják vissza None.

Véletlenszerű index kiválasztásakor csak a lista indexeinek tartományán belüli indexet válasszon. Ez azt jelenti, hogy ki kell választania egy indexet 0- tól a lista hosszáig, de nem tartalmazza. Amikor ezt a véletlen indexet hívja , a és len(values) - 1 értéketrandom.randint() kell használnia ennek a tartománynak a reprezentálására, nem pedig a len(values) -t .00

Now try to write a solution based on the information in the previous sections. If you still have trouble solving this exercise, read the Solution Template section for additional hints.

Solution Template

Try to first write a solution from scratch. But if you have difficulty, you can use the following partial program as a starting place. Copy the following code from https://invpy.com/randomshuffle-template.py and paste it into your code editor. Replace the underscores with code to make a working program:

# Import the random module for its randint() function.

import random

 

def shuffle(values):

    # Loop over the range of indexes from 0 up to the length of the list:

    for i in range(____(values)):

        # Randomly pick an index to swap with:

        swapIndex = random.randint(0, len(____) - ____)

        # Swap the values between the two indexes:

        values[i], values[swapIndex] = values[____], values[____]

The complete solution for this exercise is given in Appendix A and https://invpy.com/randomshuffle.py. You can view each step of this program as it runs under a debugger at https://invpy.com/randomshuffle-debug/.

Prev - #37 Change Maker | Table of Contents | Next - #39 Collatz Sequence