Одиночные перестановки массива

19

Вдохновленный Взятые из вопроса на переполнение стека .

Соревнование

Получив целое число n>1, выведите все массивы, которые можно получить, поменяв местами ровно две записи в массиве [1, 2, ..., n].

Массивы могут быть изготовлены в любом порядке.

Вы можете последовательно использовать [0, 1, ..., n-1](на основе 0) вместо [1, 2, ..., n](на основе 1).

Дополнительные правила

Контрольные примеры

Ввод 2дает вывод (предполагается 1 на основе)

2 1

Ввод 3дает вывод (обратите внимание, что три массива могут быть в любом порядке)

1 3 2
2 1 3
3 2 1

Ввод 4дает выход

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

Ввод 7дает выход

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
Луис Мендо
источник
Записи в индексах, заданных oeis.org/A211369, плюс один (или два, если 0-индексация) в лексикографически отсортированном списке всех перестановок длины n.
Джонатан Аллан
5
Я ценю гибкость [0 ... n-1]против [1 ... n]! Я всегда чувствую себя немного раздраженным, когда мне приходится прибегать к 1+нулю, потому что у J нулевые индексы.
Коул

Ответы:

3

Желе , 11 8 байт

ŒcżU$y€R

Попробуйте онлайн!

Как это устроено

Œ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. 
Деннис
источник
Что именно делает y? Это всегда было для меня загадкой.
января 18
Он выполняет замены. Например, [1,2],[4,3]y1,2,3заменяет каждый 1 в [1, 2, 3] на 4 , а каждый 2 на 3 .
Деннис
8

R , 54 байта

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

Попробуйте онлайн!

Возвращает матрицу, в которой каждый столбец является перестановкой.

combn(n,k)генерирует все комбинации размера kиз списка nили из одного целого числа 1:nif n. Также необязательно принимает функцию, FUNкоторая будет применена к результирующим комбинациям. Поэтому мы пишем функцию, которая выполняет обмен и возвращает список обмена. Затем все результаты накапливаются в виде array, которое в этом случае является двумерным и, следовательно, матрицей.

Giuseppe
источник
6

Haskell , 62 байта

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

Попробуйте онлайн!

Я просто генерирую перестановку, учитывая xи yпоменять местами, для каждогоx,y

H.PWiz
источник
5

Wolfram Language (Mathematica) , 43 байта

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

Попробуйте онлайн!

Объяснение: Subsets[Range@#,{2}]генерирует все подмножества {1,2,...,n}размера 2, затем для каждого подмножества /.меняет местами эти две вещи в списке {1,2,...,n}.

Этот подход неутешительно похож на многие другие представления, но вот тот, который более уникален для Mathematica, для 3 дополнительных байтов:

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

Попробуйте онлайн!

Не дерево
источник
2
Было бы еще более идиоматическое решение Mathematica ReplaceList[Range@#,{a___,b_,c___,d_,e___}:>{a,d,c,b,e}]&. Мне нравится, насколько это просто (или как непосредственно это кодирует проблему), но, к сожалению, синтаксис сопоставления с образцом настолько многословен, что в итоге получается 57 байтов.
Мартин Эндер
5

Haskell, 62 байта

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

Попробуйте онлайн!

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   
Ними
источник
4

Haskell , 71 байт

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

Попробуйте онлайн!


Это добавляет текущий номер к концу всех перестановок последнего и затем вычисляет все перестановки, которые включают новый номер.

Мастер пшеницы
источник
4

MATL , 12 байт

:2XN!"G:@tP(

Попробуйте онлайн!

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

Giuseppe
источник
1
На 2 байта короче, чем код, который я использовал для генерации тестовых случаев, и намного эффективнее :-)
Luis Mendo
@LuisMendo Как вы генерировали тестовые случаи? Я был обеспокоен тем, что мой был длиннее, так как порядок не был таким же!
Джузеппе
1
Я использовал :tY@wy=~!s2=Y). Такой же подход, как и у октавского ответа rahnema1
Луис Мендо,
3

Октава, 38 байт

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

Попробуйте онлайн!

Создает все перестановки 1: n и выбирает из них те, которые имеют два элемента, отличных от 1: n.

rahnema1
источник
2

JavaScript (ES6), 81 байт

Печатает 0-индексированные массивы.

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

демонстрация

alert()заменен console.log()на этот фрагмент для удобства использования.

Arnauld
источник
2

Чисто , 90 82 байта

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

Это может быть сделано в 80 байтах, но это превращается в прямой перевод ответов на Haskell.

Попробуйте онлайн!

Οurous
источник
2

05AB1E , 15 9 байт

LœʒD{αĀO<

Попробуйте онлайн!

объяснение

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
Emigna
источник
2

Шелуха , 9 байт

!2§kδ#≠Pḣ

Попробуйте онлайн!

объяснение

!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.
Zgarb
источник
2

Рубин , 55 53 байта

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

Попробуйте онлайн!

0-основанное решение

Хитрость в том, что внутренний цикл всегда «пропускает» итерацию: первый раз он вообще не выполняется, затем только один раз на втором проходе и так далее.

Я был счастлив с 55 байтами, пока не увидел, что R можно увеличить до 54, поэтому мне пришлось довести его до 53.

гигабайт
источник
Очень умное использование гибких выходных ограничений.
Unihedron
1

Pyth, 9 байт

t{.rLQ*=U

демонстрация

Самый простой способ поменять два значения - использовать .rфункцию ротационного перевода Пайта. .r<list>[A, B]поменяет все вхождения Aи Bв list.

Поэтому, применяя функцию перевода к UQ, список из , 0чтобы n-1с каждым списком два элемента из разных номеров в списке, мы будем генерировать желаемый результат. Qвход n, иU является функцией диапазона.

Самый простой способ сделать это:

.rLUQ.cUQ2

.cUQ2генерирует все 2 комбинации элементов различных элементов в диапазоне и .rLUQотображает .rфункцию на них и списокUQ .

Однако это будет 10 байтов.

Вместо создания .cUQ2отдельных упорядоченных пар мы можем создать все пары с *=U. Это неявно эквивалентно *=UQQ. Она начинается перезапись Qс UQ, а затем принимать декартово произведение UQиUQ . Это дает все пары чисел в диапазоне, не обязательно упорядоченные или отличные.

.rLQсвопы с использованием каждого списка. Напомним , что Qв настоящее время составит список от 0до n-1, а не n.

Поскольку пары не были заказаны, есть дубликаты. {удаляет дубликаты. Поскольку пары не были различны, неизменный список присутствует. Этот список всегда будет первым после дедупликации, поскольку {сохраняет порядок первого появления, а неизмененный список создается поворотом на [0,0]. tудаляет первый элемент, давая желаемый список перестановок.

isaacg
источник
1

Pyth, 11 байт

fq2snVTUQ.p

Попробуйте онлайн
Не такой короткий, как у Исаака, но достаточно другой для публикации.

объяснение

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.

источник
1

Java 8, 109 105 байт

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;}

Я ржавый .. Я не играл в гольф в течение нескольких месяцев .. Закончил портирование ответа @Steadybox 'C .. Возможно, еще играю в гольф.

Попробуй это здесь.

Кевин Круйссен
источник
1

Рубин , 80 байт

-12 байт благодаря 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]}

Попробуйте онлайн!

Я имел в виду подход, который лучше всего перевести на Ruby по какой-то причине, так что ... я даже не знаю Ruby ...

totallyhuman
источник
Я переиграл это: codegolf.stackexchange.com/a/152652/21830 . Сожалею!
Unihedron
Не нужно извиняться! Я думаю, что говорю от имени большинства пользователей PPCG, когда говорю, что конкуренция - это то, что делает PPCG крутым.
полностью человек
1
Что касается вашего кода, 1. вы можете назначить 1..nпеременную с одним символом и использовать ее повторно (отдельные операторы с новой строкой или точками с запятой), 2. обойтись без скобок в терминальных выражениях: i==x ?y:i==y ?x:i(обратите внимание, где у меня есть пробелы для разделения потенциального шебанга ) и 3. uniq[1,n]вместо uniq[1..-1].
Unihedron