Single swaps of an array

Luis Mendo 01/01/2018. 20 answers, 1.475 views
code-golf number combinatorics integer

Inspired by Taken from a question at Stack Overflow.

The challenge

Given an integer n>1, output all arrays that can be obtained by swapping exactly two entries in the array [1, 2, ..., n].

The arrays can be produced in any order.

You can consistently use [0, 1, ..., n-1] (0-based) instead of [1, 2, ..., n] (1-based).

Additional rules

Test cases

Input 2 gives output (assumed 1-based)

2 1

Input 3 gives output (note that the three arrays could be in any order)

1 3 2
2 1 3
3 2 1

Input 4 gives output

1 2 4 3
1 3 2 4
1 4 3 2
2 1 3 4
3 2 1 4
4 2 3 1

Input 7 gives output

1 2 3 4 5 7 6
1 2 3 4 6 5 7
1 2 3 4 7 6 5
1 2 3 5 4 6 7
1 2 3 6 5 4 7
1 2 3 7 5 6 4
1 2 4 3 5 6 7
1 2 5 4 3 6 7
1 2 6 4 5 3 7
1 2 7 4 5 6 3
1 3 2 4 5 6 7
1 4 3 2 5 6 7
1 5 3 4 2 6 7
1 6 3 4 5 2 7
1 7 3 4 5 6 2
2 1 3 4 5 6 7
3 2 1 4 5 6 7
4 2 3 1 5 6 7
5 2 3 4 1 6 7
6 2 3 4 5 1 7
7 2 3 4 5 6 1
2 Comments
Jonathan Allan 01/01/2018
Entries at indexes given by oeis.org/A211369 plus one (or two if 0-indexing) in a lexicographically sorted list of all the permutations of length n.
5 cole 01/02/2018
I appreciate the flexibility of [0 ... n-1] vs [1 ... n]! I always feel a little annoyed when I have to tack on a 1+ because J zero-indexes.

20 Answers


Giuseppe 01/01/2018.

R, 54 bytes

function(n)combn(n,2,function(x){z=1:n
z[x]=rev(x)
z})

Try it online!

Returns a matrix where each column is a permutation.

combn(n,k) generates all combinations of size k from the list n, or from 1:n if n is a single integer. It also optionally takes a function FUN to be applied to the resultant combinations. So we write a function that performs the swap and returns the swapped list. The results are then all accumulated into an array, which is in this case 2-dimensional and hence a matrix.


xnor 01/02/2018.

Python 2, 71 bytes

r=range(input())
print[map({i:j,j:i}.get,r,r)for i in r for j in r[:i]]

Try it online!

Uses this tip.


H.PWiz 01/01/2018.

Haskell, 62 bytes

f n=[[1..x-1]++y:[x+1..y-1]++x:[y+1..n]|x<-[1..n],y<-[x+1..n]]

Try it online!

I just generate the permutation, given the x and y to swap, for each x,y


Dennis 01/01/2018.

Python 2, 72 bytes

r=range(input())
for j in r:
 for i in r[:j]:t=r*1;t[i]=j;t[j]=i;print t

Try it online!


Not a tree 01/02/2018.

Wolfram Language (Mathematica), 43 bytes

r/.{#->#2,#2->#}&@@@Subsets[r=Range@#,{2}]&

Try it online!

Explanation: Subsets[Range@#,{2}] generates all subsets of {1,2,...,n} of size 2, then for each subset, /. swaps those two things in the list {1,2,...,n}.

That approach is disappointingly similar to many of the other submissions, but here's one that's more unique to Mathematica, for 3 extra bytes:

r~Permute~Cycles@{#}&/@Subsets[r=Range@#,{2}]&

Try it online!

1 comments
2 Martin Ender♦ 01/02/2018
An even more idiomatic Mathematica solution would be ReplaceList[Range@#,{a___,b_,c___,d_,e___}:>{a,d,c,b,e}]&. I like how simple it is (or how directly it encodes the problem), but unfortunately the pattern matching syntax is so verbose that this ends up being 57 bytes.

Wheat Wizard 01/01/2018.

Haskell, 71 bytes

f 0=[]
f x=map(++[x])(f$x-1)++[[1..y-1]++x:[y+1..x-1]++[y]|y<-[1..x-1]]

Try it online!


This adds the current number to the end of all the permutations of last and then computes all the swaps that include the new number.


Giuseppe 01/01/2018.

MATL, 12 bytes

:2XN!"G:@tP(

Try it online!

            %implicit input, say, 4
:           %range, stack is {[1,2,3,4]}
2           %push 2
XN          %nchoosek, compute all combinations of [1,2,3,4] taken 2 at a time
            %this results in a matrix where each row is a combination, i.e.,
            %[1, 2;
              1, 3;
              1, 4;
              2, 3;
              2, 4;
              3, 4]
!           %transpose, because "for" iterates over columns
"           %begin for loop
G:          %push input and range, stack is now [1,2,3,4]
@t          %push "for" index (the column), say, [1;2], twice
P           %flip array, so stack is now: {[1,2,3,4],[1;2],[2;1]}
(           %assignment index, sets [1,2,3,4]([1;2])=[2;1],
            %resulting in [2,1,3,4]
            %implicit end of loop, implicit end of program, print the stack implicitly.

3 comments
1 Luis Mendo 01/02/2018
2 bytes shorter than the code I used to generate the test cases, and way more effcient :-)
Giuseppe 01/02/2018
@LuisMendo How did you generate the test cases? I was worried mine was longer since the order wasn't the same!
1 Luis Mendo 01/02/2018
I used :tY@wy=~!s2=Y). Same approach as rahnema1's Octave answer, I think

nimi 01/02/2018.

Haskell, 62 bytes

g n|b<-[1..n]=[[last$k:[j|k==i]++[i|k==j]|k<-b]|i<-b,j<-b,j<i]

Try it online!

i<-b                -- loop 'i' through [1..n]
     j<-b           -- loop 'j' through [1..n]
          j<i       -- consider only cases where j<i 
 [            k<-b] -- make a list by looping 'k' through [1..n] 
  last              -- pick
          [i|k==j]  -- 'i' if k==j
       [j|k==i]     -- 'j' if k==i
     k              -- 'k' else   

Steadybox 01/01/2018.

C, 93 bytes

i,j,k;f(n){for(i=0;i++<n;)for(j=i;j++<n;puts(""))for(k=0;k++<n;)printf("%d ",k-i?k-j?k:i:j);}

Try it online!


Dennis 01/01/2018.

Jelly, 11 8 bytes

ŒcżU$y€R

Try it online!

How it works

ŒcżU$y€R  Main link. Argument: n

Œc        Take all 2-combinations of [1, ..., n].
  żU$     Zip the result with the reversed pairs.
       R  Range; yield [1, ..., n].
     y€   For each [[i, j], [j, i]] in the result to the left, yield the result to
          the right, with i replaced by j and vice versa. 
2 comments
caird coinheringaahing 01/01/2018
What exactly does y do? It's always been a bit of a mystery to me.
Dennis♦ 01/01/2018
It performs replacements. For example, [1,2],[4,3]y1,2,3 replaces each 1 in [1, 2, 3] with 4, and each 2 with 3.

rahnema1 01/02/2018.

Octave, 38 bytes

@(n)(p=perms(k=1:n))(sum(p~=k,2)==2,:)

Try it online!

Generates all permutations of 1:n and select from them those that have two elements different from 1:n.


fireflame241 01/01/2018.

Python 2, 75 bytes

lambda n:[r(i)+[j]+r(i+1,j)+[i]+r(j+1,n)for j in r(n)for i in r(j)]
r=range

Try it online!


Οurous 01/01/2018.

Clean, 90 82 bytes

import StdEnv
$n#n=[1..n]
=tl(removeDup[[if(c<>b)if(c<>a)c b a\\c<-n]\\b<-n,a<-n])

It can be done in 80 bytes, but it turns into a direct translation of the Haskell answers.

Try it online!


Emigna 01/02/2018.

05AB1E, 15 9 bytes

LœʒD{αĀO<

Try it online!

Explanation

L            # push range [1 ... input]
 œ           # get all permutations
  ʒ          # filter, keep only elements that are true when
     α       # absolute value is taken with
   D{        # a sorted copy
      Ā      # each non-zero value in the resulting array is converted to 1
       O     # the array is summed
        <    # and the sum is decremented

ovs 01/01/2018.

Python 2, 90 bytes

f=lambda n,r=range:n*[n]and[a+[n]for a in f(n-1)]+[r(1,i)+[n]+r(i+1,n)+[i]for i in r(1,n)]

Try it online!


Arnauld 01/01/2018.

JavaScript (ES6), 81 bytes

Prints 0-indexed arrays.

n=>(a=[...Array(n).keys()]).map(i=>a.map(j=>i>j&&alert(a.map(k=>k-i?k-j?k:i:j))))

Demo

alert() is replaced with console.log() in this snippet for user-friendliness.

let f =

n=>(a=[...Array(n).keys()]).map(i=>a.map(j=>i>j&&alert(a.map(k=>k-i?k-j?k:i:j))))

alert = s => console.log(JSON.stringify(s));

f(4)


totallyhuman 01/02/2018.

Ruby, 92 bytes

->n{(1..n).map{|x|(1..n).map{|y|(1..n).map{|i|(i==x)?y:(i==y)?x:i}}}.flatten(1).uniq[1..-1]}

Try it online!

I had an approach in mind that best translated to Ruby for some reason so... I don't even really know Ruby...


isaacg 01/02/2018.

Pyth, 9 bytes

t{.rLQ*=U

Demonstration

The easiest way to swap two values is to use .r, which is Pyth's rotary translation function. .r<list>[A, B] will swap all occurrences of A and B in list.

Therefore, by applying the translation function to UQ, the list from 0 to n-1 with each two element list of different numbers in the list, we will generate the desired output. Q is the input, n, and U is the range function.

The easy way to do this would be:

.rLUQ.cUQ2

.cUQ2 generates all 2 element combinations of distinct elements in the range, and .rLUQ maps the .r function over them and the list UQ.

However, that would be 10 bytes.

Instead of making .cUQ2, the distinct ordered pairs, we can make all pairs with *=U. This is implicitly equivalent to *=UQQ. It starts by overwriting Q with UQ, then taking the Cartesian product of UQ and UQ. This gives all pairs of numbers in the range, not necessarily ordered or distinct.

.rLQ swaps using each list. Recall that Q is now equal to the list from 0 to n-1, not n.

Because the pairs were not ordered, there are duplicates. { removes duplicates. Because the pairs were not distinct, the unchanged list is present. This list will always be first after deduplication, because { preserves the order of the first appearance and the unchanged list is produced by rotating by [0,0]. t removes the first element, giving the desired list of swaps.


Mnemonic 01/03/2018.

Pyth, 11 bytes

fq2snVTUQ.p

Try it online
Not as short as isaacg's approach, but different enough to post.

Explanation

fq2snVTUQ.p
         .pQ  Take the permutations of the (implicit) range [0,...,input].
f     T       Filter to get the permutations...
   snV UQ     ... where the number of differences with [0,...,input]...
 q2           ... is 2.

Kevin Cruijssen 01/04/2018.

Java 8, 109 105 bytes

n->{String r="";for(int i=0,j,k;i++<n;)for(j=i;j++<n;r+="\n")for(k=0;k++<n;)r+=k!=i?k!=j?k:i:j;return r;}

I'm rusty.. Haven't code-golfed in months.. Ended up porting @Steadybox' C answer.. Can probably be golfed some more.

Try it here.


HighResolutionMusic.com - Download Hi-Res Songs

1 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
2 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
3 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
4 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
5 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
6 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
7 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
8 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
9 Kelsea Ballerini

This Feeling flac

Kelsea Ballerini. 2018. Writer: Andrew Taggart;Alex Pall;Emily Warren.
10 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
11 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
12 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.
13 Khalid

Better flac

Khalid. 2018. Writer: Charlie Handsome;Jamil Chammas;Denis Kosiak;Tor Erik Hermansen;Mikkel Stoleer Eriksen;Khalid.
14 Lady Gaga

Look What I Found flac

Lady Gaga. 2018. Writer: DJ White Shadow;Nick Monson;Mark Nilan Jr;Lady Gaga.
15 Deep Chills

Run Free flac

Deep Chills. 2018.
16 Dynoro

In My Mind flac

Dynoro. 2018. Writer: Georgi Kay;Feenixpawl;Ivan Gough.
17 Charli XCX

1999 flac

Charli XCX. 2018. Writer: Charli XCX;Troye Sivan;Leland;Oscar Holter;Noonie Bao.
18 NCT 127

Regular (English Version) flac

NCT 127. 2018.
19 Lukas Graham

Love Someone flac

Lukas Graham. 2018. Writer: Don Stefano;Morten "Rissi" Ristorp;Morten "Pilo" Pilegaard;Jaramye Daniels;James Alan;David LaBrel;Lukas Forchhammer Graham.
20 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.

Related questions

Hot questions

Language

Popular Tags