Single swaps of an array

Question

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

• Input and output are flexible as usual.

• Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

• Shortest code in bytes wins.

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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!

Answer 5

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!

Answer 6

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   

Answer 7

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.

Answer 8

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.

Answer 9

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. 

Answer 10

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!

Answer 11

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.

Answer 12

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)

Answer 13

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!

Answer 14

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!

Answer 15

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

Answer 16

Husk, 9 bytes

!2§kδ#≠Pḣ

Try it online!

Explanation

!2§kδ#≠Pḣ  Input is an integer n.
        ḣ  Range: r=[1,2,..,n]
       P   Permutations of r.
   k       Classify by
     #     number of elements
      ≠    that are different from
  § δ      the corresponding element of r.
!2         Take the second class.

Answer 17

Ruby, 55 53 bytes

->n{n.times{|x|x.times{|y|(w=*0...n)[w[x]=y]=x;p w}}}

Try it online!

0-based solution

The trick here is that the inner loop always "skips" an iteration: the first time it's not executed at all, then only once on the second pass, and so on.

I was happy with 55 bytes until I saw that R could be golfed down to 54, so I had to get it to 53.

Answer 18

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!

Answer 19

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.

Answer 20

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.

Answer 21

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.

Answer 22

Ruby, 66 bytes

->n{a=*1..n
a.permutation.select{|b|b.zip(a).count{|c,d|c!=d}==2}}

Try it online!

Answer 23

Ruby, 80 bytes

-12 bytes thanks to Unihedron.

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

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