10
\$\begingroup\$

Write a function which takes a set of integers and prints every permutation of the set, and the swap performed in between each step

Input

a set of integers, for example (0, 1, 2)

Output

the list of permutations and swaps in the format (set) (swap) (set) ...

Test case

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)

Rules

  • You can format the set of numbers however you want.
  • You can do the swaps in any order
  • You can repeat permutations and swaps in order to get a new one
  • Your code doesn't have to actually perform the swaps, the output just needs to show what swap was made between your last output and your current one
  • Your code only needs to function for sets with 2 or more elements
  • The set you're given will have no repeating elements (e.g. (0, 1, 1, 2) is invalid)

This is code-golf, so shortest code wins!

\$\endgroup\$
  • \$\begingroup\$ Can we use randomness? \$\endgroup\$ – Zgarb Aug 24 '16 at 18:37
  • \$\begingroup\$ You mean just do a load of random swaps until you happen to achieve all permutations? Yes, but you have to be sure that all permutations have been printed \$\endgroup\$ – Billyoyo Aug 24 '16 at 18:39
  • 3
    \$\begingroup\$ Welcome to PPCG! Nice first challenge. I would suggest editing the example so the elements don't get confused with the indices, like use set (3, 1, 4) or so -- reading it the first time I was very confused because the first swap 0,1 swapped the elements 0,1 but also the indices 0,1, but then the next swap didn't follow that pattern. I'll also point you to the Sandbox where you can post challenges and get feedback before posting them to the main site. \$\endgroup\$ – AdmBorkBork Aug 24 '16 at 18:46
  • 2
    \$\begingroup\$ @TimmyD thanks for the suggestion, I have changed the example. I saw the link to the sandbox just after I posted this, I'll post there first from now on! \$\endgroup\$ – Billyoyo Aug 24 '16 at 18:49
  • 1
    \$\begingroup\$ The Steinhaus–Johnson–Trotter algorithm generates the minimum necessary sequence. \$\endgroup\$ – Neil Aug 24 '16 at 21:11
3
\$\begingroup\$

Mathematica, 102 bytes

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

Examples

//Column for a clearer result

%[{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}
*)
\$\endgroup\$
3
\$\begingroup\$

Java, 449 426 bytes

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+")");}}

Brute force approach. It keeps making random swaps until all the possible permutations have took place. It uses a Set of the string representation of the array in order to check how many different states have been generated. For n different integers there are n! = 1*2*3*..*n distinct permutations.

Update

  • Followed Kevin Cruijssen's suggestions to golf it a bit more.

Ungolfed:

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 + ")");
    }
}

Usage:

$ 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]

As you can see there are many more swaps than the necessary minimum. But it seems to work :-D

As a bonus, it works with strings too, i.e.

$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]
\$\endgroup\$
  • \$\begingroup\$ do you have an un-golfed version for us to take a look at your method using? \$\endgroup\$ – Billyoyo Aug 24 '16 at 21:43
  • \$\begingroup\$ @Billyoyo: Added the un-golfed code. Nothing fancy there however :-) \$\endgroup\$ – Master_ex Aug 24 '16 at 21:56
  • \$\begingroup\$ You can golf it a bit. No need to fix warnings, so you can removed the Set declarations: Set s=new HashSet();. Your code in the method n can be a single return: static int n(int x){return x==1?1:x*n(x-1);}. And you can replace String z in your method o with a generic instead: static<T>void o(T z){System.out.println(z);s.add(z);}. All combined it would get down to 426 bytes. \$\endgroup\$ – Kevin Cruijssen Aug 25 '16 at 14:52
1
\$\begingroup\$

JavaScript (ES6), 186 bytes

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`,`)>

Note: I'm not sure how flexible the output format is, may be I could do this for 171 bytes:

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}

Works by performing the Steinhaus–Johnson–Trotter algorithm on the shuffle array of indices and translating back to the input array. Ungolfed:

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
}
\$\endgroup\$
1
\$\begingroup\$

Ruby, 86 bytes

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

Haskell - 135 bytes

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

output:

> 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))]

I am using the standard permutations function, which is not based on swaps, so I am taking the permutations of the permutations and finding one that happens to be a chain of swaps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.