19
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Allan Jan 1 '18 at 23:50
  • 5
    \$\begingroup\$ 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. \$\endgroup\$ – cole Jan 2 '18 at 1:01

23 Answers 23

3
\$\begingroup\$

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. 
\$\endgroup\$
  • \$\begingroup\$ What exactly does y do? It's always been a bit of a mystery to me. \$\endgroup\$ – caird coinheringaahing Jan 1 '18 at 22:37
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Jan 1 '18 at 22:40
8
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Jan 2 '18 at 9:37
5
\$\begingroup\$

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

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 2 bytes shorter than the code I used to generate the test cases, and way more effcient :-) \$\endgroup\$ – Luis Mendo Jan 2 '18 at 0:01
  • \$\begingroup\$ @LuisMendo How did you generate the test cases? I was worried mine was longer since the order wasn't the same! \$\endgroup\$ – Giuseppe Jan 2 '18 at 15:15
  • 1
    \$\begingroup\$ I used :tY@wy=~!s2=Y). Same approach as rahnema1's Octave answer, I think \$\endgroup\$ – Luis Mendo Jan 2 '18 at 19:48
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Very clever use of flexible output constraints. \$\endgroup\$ – Unihedron Jan 5 '18 at 22:47
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

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.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 66 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I outgolfed this: codegolf.stackexchange.com/a/152652/21830. Sorry! \$\endgroup\$ – Unihedron Jan 5 '18 at 19:41
  • \$\begingroup\$ No need to apologize! I think I speak for most PPCG users when I say that the competition is what makes PPCG cool. \$\endgroup\$ – totallyhuman Jan 5 '18 at 19:43
  • 1
    \$\begingroup\$ As for your code, 1. you could assign 1..n to a one-char variable and reuse it (separate statements with newline or semicolons), 2. do without brackets in the termary statements: i==x ?y:i==y ?x:i (note where I have the spaces to seperate the potential shebang) and 3. uniq[1,n] instead of uniq[1..-1]. \$\endgroup\$ – Unihedron Jan 5 '18 at 19:50

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.