Langkah Permutasi

10

Tulis fungsi yang mengambil satu set integer dan mencetak setiap permutasi set, dan swap dilakukan di antara setiap langkah

Memasukkan

seperangkat bilangan bulat, misalnya (0, 1, 2)

Keluaran

daftar permutasi dan swap dalam format (set) (swap) (set) ...

Kasus cobaan

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)

Aturan

  • Anda dapat memformat set angka sesuai keinginan Anda.
  • Anda dapat melakukan swap dalam urutan apa pun
  • Anda dapat mengulangi permutasi dan swap untuk mendapatkan yang baru
  • Kode Anda tidak harus benar-benar melakukan swap, output hanya perlu menunjukkan swap apa yang dibuat antara output terakhir Anda dan yang Anda miliki saat ini
  • Kode Anda hanya perlu berfungsi untuk set dengan 2 elemen atau lebih
  • Set yang Anda berikan tidak akan memiliki elemen berulang (mis. (0, 1, 1, 2) tidak valid)

Ini kode-golf, jadi kode terpendek menang!

Billyoyo
sumber
Bisakah kita menggunakan keacakan?
Zgarb
Maksud Anda hanya melakukan banyak swap acak sampai Anda mencapai semua permutasi? Ya, tetapi Anda harus yakin bahwa semua permutasi telah dicetak
Billyoyo
3
Selamat datang di PPCG! Tantangan pertama yang bagus. Saya akan menyarankan mengedit contoh sehingga elemen tidak bingung dengan indeks, seperti menggunakan set (3, 1, 4)atau lebih - membacanya pertama kali saya sangat bingung karena swap pertama 0,1bertukar elemen 0,1tetapi juga indeks 0,1, tetapi kemudian berikutnya swap tidak mengikuti pola itu. Saya juga akan mengarahkan Anda ke Sandbox di mana Anda dapat memposting tantangan dan mendapatkan umpan balik sebelum mempostingnya ke situs utama.
AdmBorkBork
2
@TimmyD terima kasih atas sarannya, saya telah mengubah contohnya. Saya melihat tautan ke kotak pasir tepat setelah saya memposting ini, saya akan memposting di sana dulu mulai sekarang!
Billyoyo
1
The Steinhaus-Johnson-Trotter algoritma menghasilkan urutan minimum yang diperlukan.
Neil

Jawaban:

3

Mathematica, 102 byte

<<Combinatorica`
Riffle[#,BlockMap[Pick[#[[1]],#!=0&/@({1,-1}.#)]&,#,2,1]]&@*MinimumChangePermutations

Contohnya

// Kolom untuk hasil yang lebih jelas

%[{1,3,5}]//Column
(*
{1,3,5}
{1,3}
{3,1,5}
{3,5}
{5,1,3}
{5,1}
{1,5,3}
{1,3}
{3,5,1}
{3,5}
{5,3,1}
*)
njpipeorgan
sumber
3

Java, 449 426 byte

import java.util.*;interface P{static Set s=new HashSet();static void main(String[]a){o(Arrays.toString(a));while(s.size()<n(a.length)){p(a);o(Arrays.toString(a));}}static<T>void o(T z){System.out.println(z);s.add(z);}static int n(int x){return x==1?1:x*n(x-1);}static void p(String[]a){Random r=new Random();int l=a.length,j=r.nextInt(l),i=r.nextInt(l);String t=a[j];a[j]=a[i];a[i]=t;System.out.println("("+a[j]+","+t+")");}}

Pendekatan kekerasan. Itu terus membuat swap acak sampai semua permutasi yang mungkin terjadi. Ini menggunakan Set representasi string dari array untuk memeriksa berapa banyak negara yang berbeda telah dihasilkan. Untuk n bilangan bulat yang berbeda ada n! = 1 * 2 * 3 * .. * n permutasi yang berbeda.

Memperbarui

  • Ikuti saran Kevin Cruijssen untuk bermain golf sedikit lebih banyak.

Tidak Disatukan:

import java.util.*;

interface P {

    static Set<String> s = new HashSet<>();

    static void main(String[] a) {
        // prints the original input
        o(Arrays.toString(a));
        while (s.size() < n(a.length)) {
            p(a);
            // prints the array after the swap
            o(Arrays.toString(a));
        }
    }

    static void o(String z) {
        System.out.println(z);
        // adds the string representation of the array to the HashSet
        s.add(z);
    }

    // method that calculates n!
    static int n(int x) {
        if (x == 1) {
            return 1;
        }
        return x * n(x - 1);
    }

    // makes a random swap and prints what the swap is
    static void p(String[] a) {
        Random r = new Random();
        int l = a.length, j = r.nextInt(l), i = r.nextInt(l);
        String t = a[j];
        a[j] = a[i];
        a[i] = t;
        System.out.println("(" + a[j] + "," + t + ")");
    }
}

Pemakaian:

$ javac P.java
$ java P 1 2 3
[1, 2, 3]
(2,1)
[2, 1, 3]
(1,1)
[2, 1, 3]
(2,2)
[2, 1, 3]
(3,1)
[2, 3, 1]
(3,1)
[2, 1, 3]
(1,2)
[1, 2, 3]
(1,1)
[1, 2, 3]
(3,2)
[1, 3, 2]
(2,3)
[1, 2, 3]
(3,1)
[3, 2, 1]
(3,1)
[1, 2, 3]
(3,3)
[1, 2, 3]
(1,2)
[2, 1, 3]
(1,3)
[2, 3, 1]
(1,2)
[1, 3, 2]
(3,1)
[3, 1, 2]

Seperti yang Anda lihat ada banyak swap lebih dari minimum yang diperlukan. Tapi sepertinya berhasil :-D

Sebagai bonus, ia bekerja dengan string juga, yaitu

$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]
Master_ex
sumber
apakah Anda memiliki versi yang tidak golf agar kami dapat melihat metode Anda menggunakan?
Billyoyo
@Billyoyo: Menambahkan kode un-golfed. Tidak ada yang mewah di sana :-)
Master_ex
Anda bisa bermain golf sedikit. Tidak perlu peringatan memperbaiki, sehingga Anda dapat dihapus deklarasi Set: Set s=new HashSet();. Kode Anda dalam metode ndapat kembali tunggal: static int n(int x){return x==1?1:x*n(x-1);}. Dan Anda dapat mengganti String zmetode Anda odengan generik bukan: static<T>void o(T z){System.out.println(z);s.add(z);}. Semua digabungkan akan turun ke 426 byte .
Kevin Cruijssen
1

JavaScript (ES6), 186 byte

f=
a=>{console.log(a);d=a.slice().fill(-1);s=[...d.keys()];for(i=l=a.length;i;)s[k=(j=s.indexOf(--i))+d[i]]<i?(console.log(a[s[j]=s[k]],a[s[k]=i]),console.log(s.map(n=>a[n])),i=l):d[i]*=-1}
;
<input id=i><input type=button value=Go! onclick=f(i.value.split`,`)>

Catatan: Saya tidak yakin seberapa fleksibel format outputnya, mungkin saya bisa melakukan ini untuk 171 byte:

a=>{console.log(a);d=a.slice().fill(-1);s=[...d.keys()];for(i=l=a.length;i;)s[k=(j=s.indexOf(--i))+d[i]]<i?console.log(a[s[j]=s[k]],a[s[k]=i],s.map(n=>a[n],i=l)):d[i]*=-1}

Bekerja dengan melakukan algoritma Steinhaus – Johnson – Trotter pada array shuffle indeks dan menerjemahkan kembali ke array input. Tidak Disatukan:

function steps(array) {
    console.log(array); // initial row
    var d = a.slice().fill(-1); // direction values
    var s = [...a.keys()]; // initial (identity) shuffle
    var l = a.length;
    for (var i = l; i; ) { // start by trying to move the last element
        var j = s.indexOf(--i);
        var k = j + d[i]; // proposed exchange
        if (s[k] < i) { // only exchange with lower index (within bounds)
            console.log(a[s[k]],a[i]); // show values being exchanged
            s[j] = s[k];
            s[k] = i; // do the exchange on the shuffle
            console.log(s.map(n=>a[n])); // show the shuffled array
            i = l; // start from the last element again
        } else {
            d[i] *= -1; // next time, try moving it the other way
        } // --i above causes previous element to be tried
    } // until no movable elements can be found
}
Neil
sumber
1

Ruby, 86 byte

puts (2..(a=gets.scan(/\d+/).uniq).size).map{|i|a.permutation(i).map{|e|?(+e*", "+?)}}
cia_rana
sumber
1

Haskell - 135 byte

p=permutations;f=filter
q(a:b:xs)=(\x->f(uncurry(/=)).zip x)a b:q(b:xs);q _=[]
l=head.f(all((==2).length).q).p.p
f=zip.l<*>map head.q.l

keluaran:

> f [3,1,5]
[([3,1,5],(3,1)),([1,3,5],(3,5)),([1,5,3],(1,5)),([5,1,3],(1,3)),([5,3,1],(5,3))]

Saya menggunakan permutationsfungsi standar , yang tidak didasarkan pada swap, jadi saya mengambil permutasi permutasi dan menemukan satu yang kebetulan merupakan rantai swap.

BlackCap
sumber