# Single swaps of an array

Luis Mendo 01/01/2018. 20 answers, 1.475 views

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

# 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
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.

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.

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!

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.

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   

# 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 =

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.