Napisz funkcję, która pobiera zestaw liczb całkowitych i wypisuje każdą permutację zestawu, a zamiana jest wykonywana pomiędzy każdym krokiem
Wejście
zestaw liczb całkowitych, na przykład (0, 1, 2)
Wynik
lista permutacji i zamian w formacie (zestaw) (zamiana) (zestaw) ...
Przypadek testowy
Input:
(3, 1, 5)
Output:
(3, 1, 5)
(3, 1)
(1, 3, 5)
(3, 5)
(1, 5, 3)
(1, 3)
(3, 5, 1)
(3, 5)
(5, 3, 1)
(3, 1)
(5, 1, 3)
Zasady
- Możesz sformatować zestaw liczb w dowolny sposób.
- Możesz wykonywać swapy w dowolnej kolejności
- Możesz powtarzać permutacje i zamiany, aby uzyskać nową
- Twój kod nie musi tak naprawdę wykonywać swapów, dane wyjściowe muszą tylko pokazywać, co zostało zrobione między ostatnim a ostatnim wyjściem
- Twój kod musi działać tylko w przypadku zestawów zawierających 2 lub więcej elementów
- Podany zestaw nie będzie zawierał powtarzających się elementów (np. (0, 1, 1, 2) jest nieprawidłowy)
To jest golf golfowy, więc wygrywa najkrótszy kod!
code-golf
math
permutations
Billyoyo
źródło
źródło
(3, 1, 4)
lub tak - czytając go za pierwszym razem byłem bardzo zdezorientowany, ponieważ pierwsza zamiana0,1
zamieniła elementy,0,1
ale także indeksy0,1
, ale potem następna swap nie postępował zgodnie z tym wzorem. Wskażę ci także piaskownicę, w której możesz publikować wyzwania i uzyskiwać opinie przed opublikowaniem ich na głównej stronie.Odpowiedzi:
Mathematica, 102 bajty
Przykłady
// Kolumna dla wyraźniejszego wyniku
źródło
Java,
449426 bajtówPodejście brutalnej siły. Wykonuje losowe zamiany, dopóki nie zostaną wykonane wszystkie możliwe permutacje. Używa zestawu reprezentacji ciągu tablicy, aby sprawdzić, ile różnych stanów zostało wygenerowanych. Dla n różnych liczb całkowitych jest n! = 1 * 2 * 3 * .. * n odrębne permutacje.
Aktualizacja
Nie golfowany:
Stosowanie:
Jak widać, jest o wiele więcej swapów niż niezbędne minimum. Ale wydaje się, że działa :-D
Jako bonus działa również z łańcuchami, tj
źródło
Set s=new HashSet();
. Twój kod w metodzien
może być pojedynczy zwrot:static int n(int x){return x==1?1:x*n(x-1);}
. I można wymienićString z
w sposóbo
rodzajowy zamiast:static<T>void o(T z){System.out.println(z);s.add(z);}
. Wszystko razem spadłoby do 426 bajtów .JavaScript (ES6), 186 bajtów
Uwaga: Nie jestem pewien, jak elastyczny jest format wyjściowy, być może mógłbym to zrobić dla 171 bajtów:
Działa poprzez wykonanie algorytmu Steinhaus – Johnson – Trotter na tablicy losowej indeksów i przełożenie z powrotem na tablicę wejściową. Nie golfowany:
źródło
Rubinowy, 86 bajtów
źródło
Haskell - 135 bajtów
wynik:
Korzystam ze standardowej
permutations
funkcji, która nie jest oparta na zamianie, więc biorę permutacje permutacji i znajduję taką, która jest łańcuchem swapów.źródło