Разложить перестановку на циклы

15

Хорошо известна теорема о том, что любая перестановка может быть разложена на множество циклов . Ваша задача - написать максимально короткую программу для этого.

Входные данные:

Две строчки Первый содержит число N, второй содержит Nразличные целые числа в диапазоне, [0,N-1]разделенные пробелами. Эти целые числа представляют перестановку Nэлементов.

Выход:

Одна строка для каждого цикла в перестановке. Каждая строка должна быть разделенным пробелами списком целых чисел в порядке цикла.

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

Пример 1:

8
2 3 4 5 6 7 0 1

Этот вход кодирует перестановку 0-> 2, 1-> 3, 2-> 4, 3-> 5, 4-> 6, 5-> 7, 6-> 0, 7-> 1. Это разлагается на циклы, как это:

0 2 4 6
1 3 5 7

В равной степени действительный результат будет

5 7 1 3
2 4 6 0

Пример 2:

8
0 1 3 4 5 6 7 2

действительный вывод:

0
1
4 5 6 7 2 3
code-golf math combinatorics permutations Кит Рэндалл
источник
@Keith Какое максимальное значение N?
fR0DDY
3
3 символа в J:>C.
Eelvex
Допустим, N <1000.
Кит Рэндалл
Перестановки обычно считаются с 1, а не с 0.
Доктор Белизарий
6
Математики считают от 1, программисты считают от 0 :)
Кит Рэндалл

Ответы:

4

C 145 134 символов

N,A[999],i,j,f;main(){gets(&i);for(;~scanf("%d",A+N);)N++;for(;j<N;j++,f=f&&!puts(""))while(i=A[j]+1)f=printf("%d ",j),A[j]=-1,j=--i;}

http://www.ideone.com/BrWJT

fR0DDY
источник
Законно ли вызывать неявно объявленные функции с переменными числами? Законно ли сначала опускать int?
6502
Законно делать что-либо, пока работает код. Хотя он может выдавать предупреждения, если он не дает ошибок, все должно быть в порядке.
fR0DDY
Суть в том, что означает «работает». Как бы то ни было, я добавил ответ (139 символов), в котором используется это правило (т. Е. Там, где «работает» означает «есть хотя бы один самопровозглашенный компилятор C, в котором, по-видимому, сгенерированный машинный код работает»)
6502
+1: мне нравится gets(&i)идея избавиться от этой бесполезной первой строки, однако это явно не сработает на 16-битных системах, если передано более 10 элементов. Но еще раз, если правила «находят, по крайней мере, программу, которая претендует на то, чтобы быть компилятором C, которая создает исполняемый файл, где, по крайней мере, в одном случае кажется - по крайней мере, мне - дать правильный ответ», тогда это улучшение: )
6502
2

Python 131 символ

input();d=dict((i,int(x))for i,x in enumerate(raw_input().split()))
while d:
 x=list(d)[0]
 while x in d:print x,;x=d.pop(x)
 print

окончание новой строки не требуется

6502
источник
1

Хаскель, 131 персонаж

n%l|all(>n)l=(n:l>>=(++" ").show)++"\n"|1<3=""
c(_:a)=a>>=(\n->n%(takeWhile(/=n)$iterate(a!!)$a!!n))
main=interact$c.map read.words
  • Изменить: (135 -> 131) >=стал >, устранены два tailвызова, хотя сопоставление с образцом и предварительное применение a!!.
MtnViewMark
источник
1

С (вроде), 139 символов

n,j,t,a[999];main(){scanf("%*i");for(;scanf("%i",a+n)>0;)n++;while(n--)if(a[j=n]+1){for(;t=a[j]+1;a[j]=-1,j=t)printf("%i ",--t);puts("");}}

Финальный перевод строки не включен.

Я сказал "вроде", потому что AFAIK, например,

  1. недопустимо опускать объявление для функций с переменным числом (ANSI C89: 3.3.2.2)
  2. intне может быть опущено для объявления переменной (я не нашел, где сказано, что это может быть опущено, и неявное объявление типа описано только для функций. Спецификация грамматики в стандарте в основном бесполезна, так как принимает намного больше, чем допустимые объявления C, например double double void volatile x;)
  3. обязательный символ новой строки в конце непустого исходного файла (ANSI C89: A.6.2)

но приведенный выше код, скомпилированный с, по- gcc -ocycles cycles.cвидимому, работает в любом случае.

6502
источник
Это действительная программа на C, но это не C99.
Quixotic
@Debanjan: Нет, это не ANSI C (даже не 89). Например, стандарт гласит (3.3.2.2), что если функция использует переменное количество аргументов, то она не может быть объявлена ​​неявно на сайте вызова функции (другими словами, вы не можете вызывать scanfбез нее, #include <stdio.h>даже если параметры верны и не требуют преобразований ):<<If the function is defined with a type that includes a prototype, and the types of the arguments after promotion are not compatible with the types of the parameters, or if the prototype ends with an ellipsis ( ", ..." ), the behavior is undefined.>>
6502
1

J (от 2 до 32)

Я не совсем ясно о формате ввода / C.вывода , но я думаю, что будет, если будет принят следующий вывод:

   C. 0 1 3 4 5 6 7 2
┌─┬─┬───────────┐
│0│1│7 2 3 4 5 6│
└─┴─┴───────────┘

(В терминале J выглядит лучше.)

Если это должна быть именованная функция, которая соответствует моему лучшему пониманию формата ввода-вывода, то это будет 32 символа, из которых 30 для преобразования выходного формата ...

g=:>@(":L:0)@(C.@".@}.~>:@i.&LF)

В бою:

   g=:>@(":L:0)@(C.@".@}.~>:@i.&LF)
   g
>@(":L:0)@(C.@".@}.~ >:@i.&(10{a.))
   t
8
0 1 3 4 5 6 7 2
   g t
0          
1          
7 2 3 4 5 6

Объяснение:

J выполняется справа налево (практически). @это «функция» (технически не функция, но это достаточно близко) для объединения функций.

  • i.&LF- найти первый индекс LF, предопределенную переменную, содержащую символ ASCII номер 10, перевод строки.
  • >:- найти первое LFи увеличить его индекс на единицу. На самом деле нам не нужен перевод строки, нам нужен массив, следующий за ним.
  • }.~ - Выбирает ту часть ввода, которую мы хотим.
  • ".- Поскольку формат ввода действителен J ( * \ х / * ), мы можем просто использовать evalглагол (я знаю, что он на самом деле не вызывается eval.), Чтобы превратить его в массив
  • C.- Чистая магия. Я действительно понятия не имею, что это делает, но, похоже, работает!
  • ":L:0- Представление. Превращает вывод C.в упакованную последовательность строк
  • >- Распаковать. Фактический вывод - это строковый массив (за первым номером стоят пробелы).
ɐɔıʇǝɥʇuʎs
источник
0

Clojure, 145

(let[v(vec(repeatedly(read)read))](loop[a(set v)b 0](cond(a(v b))(do(print" "b)(recur(disj a(v b))(v b)))(seq a)(do(prn)(recur a(first a)))1"")))

В некоторой степени не разобрано и разбито на функцию (вход должен быть вектором, который и производит (vec (многократно (читается))) сверху):

(defn p [v]
  (loop [a (set v) b 0]
    (cond
     (a (v b)) (do (print" "b) (recur (disj a (v b)) (v b)))
     (seq a) (do (prn) (recur a (first a)))
     1 "")))

(Ух ты, только что заметил, что этому заданию уже более 3 лет. Ну да ладно, в любом случае было весело!)

YosemiteMark
источник