W Pythonie tasowanie sekwencji liczb zawsze było użytecznym narzędziem i pytaniem, które pojawiało się również podczas wielu rozmów kwalifikacyjnych w firmie. Znajomość więcej niż jednej metody osiągnięcia tego zawsze może być zaletą. Omówmy pewne sposoby, w jakie można to osiągnąć.

Losowe losowe przetasowanie listy w Pythonie

W Pyton, istnieje kilka sposobów przetasowania listy. Oto różne sposoby Pythona na tasowanie list.

• Korzystanie z sortowanej()
• Używanie random.shuffle()
• Używanie random.sample()
• Korzystanie z metody losowego wyboru
• Korzystanie z algorytmu tasowania Fishera-Yatesa
• Korzystanie z funkcji itertools.permutations().
• Korzystanie z NumPy

Losowe przetasowanie listy za pomocą sorted()

Posortowaną wersję listy można utworzyć za pomocą metody posortowane() funkcjonować. Skutecznie tasujemy elementy losowo, używając ich na kopii przetasowanej listy.

Python3

import> random> my_list> => [> 1> ,> 2> ,> 3> ,> 4> ,> 5> ]> shuffled_list> => sorted> (my_list, key> => lambda> x: random.random())> print> (> 'Original list:'> , my_list)> print> (> 'Shuffled list:'> , shuffled_list)>

Wyjście

Original list: [1, 2, 3, 4, 5] Shuffled list: [2, 3, 4, 5, 1] 

Złożoność czasowa: O(nlogn), gdzie n jest długością listy
Złożoność przestrzeni: O(n), gdzie n jest długością listy

Losuj listę za pomocą Random.Shuffle()

Losowo. Losowo() to najbardziej zalecana metoda tasowania listy. Python w swojej losowej bibliotece udostępnia tę wbudowaną funkcję, która na miejscu tasuje listę. Wadą tego jest to, że w tym procesie traci się kolejność list. Przydatne dla programistów, którzy chcą zaoszczędzić czas i wysiłek.

Python3

import> random> test_list> => [> 1> ,> 4> ,> 5> ,> 6> ,> 3> ]> print> (> 'The original list is : '> +> str> (test_list))> # using random.shuffle() to shuffle a list> random.shuffle(test_list)> print> (> 'The shuffled list is : '> +> str> (test_list))>

Wyjście

The original list is : [1, 4, 5, 6, 3] The shuffled list is : [5, 1, 3, 4, 6] 

Złożoność czasowa: O(n), gdzie n jest długością listy
Złożoność przestrzeni: O(n), gdzie n jest długością listy

Losuj listę u śpiewaj Random.Sample()

Losowa próbka(), Jest to całkiem przydatna funkcja, lepsza niż metoda tasowania zastosowana powyżej w tym sensie, że tworzy nową przetasowaną listę i zwraca ją, zamiast zakłócać porządek oryginalnej listy. Jest to przydatne w przypadkach, gdy chcemy zachować oryginalną listę.

Python3

import> random> test_list> => [> 1> ,> 4> ,> 5> ,> 6> ,> 3> ]> print> (> 'The original list is : '> +> str> (test_list))> # using random.sample()to shuffle a list> res> => random.sample(test_list,> len> (test_list))> print> (> 'The shuffled list is : '> +> str> (res))>

Wyjście

The original list is : [1, 4, 5, 6, 3] The shuffled list is : [4, 3, 1, 6, 5] 

Złożoność czasowa: O(n), gdzie n jest długością listy
Złożoność przestrzeni: O(n), gdzie n jest długością listy

Losuj listę za pomocą metody losowego wyboru

W tej metodzie będziemy losować listę za pomocą metoda losowego wyboru . Wybieramy indeks losowo i dołączamy ten element do listy.

Python3

import> random> arr> => [> 1> ,> 2> ,> 3> ,> 4> ,> 5> ,> 6> ]> print> (> 'Original List: '> , arr)> n> => len> (arr)> for> i> in> range> (n):> > j> => random.randint(> 0> , n> -> 1> )> > element> => arr.pop(j)> > arr.append(element)> > print> (> 'Shuffled List: '> , arr)>

Wyjście

Original List: [1, 2, 3, 4, 5, 6] Shuffled List: [1, 5, 2, 6, 3, 4] 

Złożoność czasowa: O(n) gdzie n jest długością listy
Złożoność przestrzeni: O(1)

Losowe przetasowanie listy przy użyciu algorytmu przetasowania Fishera-Yatesa

Jest to jeden ze znanych algorytmów Algorytm tasowania Fishera-Yatesa , używany głównie do tasowania sekwencji liczb w Pythonie. Algorytm ten po prostu pobiera wyższą wartość indeksu i zamienia ją z bieżącą wartością, proces ten powtarza się w pętli aż do końca listy.

Python3

import> random> test_list> => [> 1> ,> 4> ,> 5> ,> 6> ,> 3> ]> print> (> 'The original list is : '> +> str> (test_list))> # using Fisher–Yates shuffle Algorithm to shuffle a list> for> i> in> range> (> len> (test_list)> -> 1> ,> 0> ,> -> 1> ):> > # Pick a random index from 0 to i> > j> => random.randint(> 0> , i> +> 1> )> > # Swap arr[i] with the element at random index> > test_list[i], test_list[j]> => test_list[j], test_list[i]> print> (> 'The shuffled list is : '> +> str> (test_list))>

Wyjście

The original list is : [1, 4, 5, 6, 3]The shuffled list is : [3, 4, 5, 6, 1] 

Złożoność czasowa: O(n), gdzie n jest długością listy
Złożoność przestrzeni: O(n), gdzie n jest długością listy

Losuj listę za pomocą funkcji Itertools.Permutations().

Ta metoda generuje wszystkie możliwe permutacje oryginalnej listy za pomocą itertools.permutations() funkcję, a następnie wybierz losową.

Python3

import> random> import> itertools> lst> => [> 1> ,> 4> ,> 5> ,> 6> ,> 3> ]> permutations> => list> (itertools.permutations(lst))> shuffled_lst> => random.choice(permutations)> print> (> 'Shuffled list:'> , shuffled_lst)>

Wyjście

Shuffled list: (6, 5, 4, 1, 3) 

Złożoność czasowa: O(n!) gdzie n jest długością listy, wynikającą z wygenerowania wszystkich możliwych permutacji.
Złożoność przestrzeni: O(n!), ponieważ wszystkie możliwe permutacje są generowane i przechowywane na liście.

Losuj listę za pomocą Numpy’ego

Używamy NumPy() aby przetasować elementy na liście. Aby losować listę za pomocą numpy, musimy przekonwertować listę na tablicę NumPy, a następnie zastosować funkcję zmniejszania, która zwraca przetasowaną listę i drukuje przetasowaną listę.

Python3

import> numpy as np> from> functools> import> reduce> test_list> => [> 1> ,> 4> ,> 5> ,> 6> ,> 3> ]> # Printing original list> print> (> 'The original list is : '> +> str> (test_list))> # using reduce() and numpy to shuffle a list> res> => reduce> (> lambda> acc, _: np.random.permutation(acc),> > range> (> len> (test_list)), np.array(test_list))> print> (> 'The shuffled list is : '> +> str> (res.tolist()))>

Wyjście

The original list is : [1, 4, 5, 6, 3] The shuffled list is : [3, 6, 1, 5, 4] 

Złożoność czasowa: Złożoność czasowa funkcji redukcji() zależy od liczby iteracji, która jest równa długości listy. Złożoność czasowa np.random.permutation() wynosi O(n), gdzie n jest długością tablicy wejściowej. Dlatego złożoność czasowa tego kodu wynosi O(n^2).
Złożoność przestrzeni: Złożoność przestrzenna tego kodu zależy od rozmiaru listy. Lista jest przechowywana w pamięci wraz z kilkoma dodatkowymi zmiennymi używanymi przez funkcję redukcji(). Dlatego złożoność przestrzenna wynosi O (n).