Чередование последовательностей

18

Чередующиеся последовательности представляют собой произвольное слияние некоторого количества последовательностей.

Последовательность с чередованием может быть выполнена путем добавления элементов в список один за другим из некоторого числа списков, каждый раз выбирая следующий элемент из некоторого списка. Следовательно, чередующаяся последовательность будет содержать одинаковые элементы всех списков, объединенных в порядке, согласованном со всеми списками.

Единственное чередование 1 списка - это тот же список.

Вызов

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

Примеры

Input: [1, 2], [3, 4]
Output:
    [1, 2, 3, 4]
    [1, 3, 2, 4]
    [1, 3, 4, 2] 
    [3, 1, 2, 4]
    [3, 1, 4, 2]
    [3, 4, 1, 2]

Input: [1, 2, 3, 4, 5]
Output:
    [1, 2, 3, 4, 5]

Input: []
Output:
    []

Input: <nothing>
Output:
    []

(also acceptable)
Input: <nothing>
Output: <nothing>

Input: [1, 2, 3], [4, 5]
Output:
    [1, 2, 3, 4, 5]
    [1, 2, 4, 3, 5]
    [1, 2, 4, 5, 3]
    [1, 4, 2, 3, 5]
    [1, 4, 2, 5, 3]
    [1, 4, 5, 2, 3]
    [4, 1, 2, 3, 5]
    [4, 1, 2, 5, 3]
    [4, 1, 5, 2, 3]
    [4, 5, 1, 2, 3]

Input: [1, 2], [3, 4], [5, 6]
Output:
    [1, 2, 3, 4, 5, 6]
    [1, 2, 3, 5, 4, 6]
    [1, 2, 3, 5, 6, 4]
    [1, 2, 5, 3, 4, 6]
    [1, 2, 5, 3, 6, 4]
    [1, 2, 5, 6, 3, 4]
    [1, 3, 2, 4, 5, 6]
    [1, 3, 2, 5, 4, 6]
    [1, 3, 2, 5, 6, 4]
    [1, 3, 4, 2, 5, 6]
    [1, 3, 4, 5, 2, 6]
    [1, 3, 4, 5, 6, 2]
    [1, 3, 5, 2, 4, 6]
    [1, 3, 5, 2, 6, 4]
    [1, 3, 5, 4, 2, 6]
    [1, 3, 5, 4, 6, 2]
    [1, 3, 5, 6, 2, 4]
    [1, 3, 5, 6, 4, 2]
    [1, 5, 2, 3, 4, 6]
    [1, 5, 2, 3, 6, 4]
    [1, 5, 2, 6, 3, 4]
    [1, 5, 3, 2, 4, 6]
    [1, 5, 3, 2, 6, 4]
    [1, 5, 3, 4, 2, 6]
    [1, 5, 3, 4, 6, 2]
    [1, 5, 3, 6, 2, 4]
    [1, 5, 3, 6, 4, 2]
    [1, 5, 6, 2, 3, 4]
    [1, 5, 6, 3, 2, 4]
    [1, 5, 6, 3, 4, 2]
    [3, 1, 2, 4, 5, 6]
    [3, 1, 2, 5, 4, 6]
    [3, 1, 2, 5, 6, 4]
    [3, 1, 4, 2, 5, 6]
    [3, 1, 4, 5, 2, 6]
    [3, 1, 4, 5, 6, 2]
    [3, 1, 5, 2, 4, 6]
    [3, 1, 5, 2, 6, 4]
    [3, 1, 5, 4, 2, 6]
    [3, 1, 5, 4, 6, 2]
    [3, 1, 5, 6, 2, 4]
    [3, 1, 5, 6, 4, 2]
    [3, 4, 1, 2, 5, 6]
    [3, 4, 1, 5, 2, 6]
    [3, 4, 1, 5, 6, 2]
    [3, 4, 5, 1, 2, 6]
    [3, 4, 5, 1, 6, 2]
    [3, 4, 5, 6, 1, 2]
    [3, 5, 1, 2, 4, 6]
    [3, 5, 1, 2, 6, 4]
    [3, 5, 1, 4, 2, 6]
    [3, 5, 1, 4, 6, 2]
    [3, 5, 1, 6, 2, 4]
    [3, 5, 1, 6, 4, 2]
    [3, 5, 4, 1, 2, 6]
    [3, 5, 4, 1, 6, 2]
    [3, 5, 4, 6, 1, 2]
    [3, 5, 6, 1, 2, 4]
    [3, 5, 6, 1, 4, 2]
    [3, 5, 6, 4, 1, 2]
    [5, 1, 2, 3, 4, 6]
    [5, 1, 2, 3, 6, 4]
    [5, 1, 2, 6, 3, 4]
    [5, 1, 3, 2, 4, 6]
    [5, 1, 3, 2, 6, 4]
    [5, 1, 3, 4, 2, 6]
    [5, 1, 3, 4, 6, 2]
    [5, 1, 3, 6, 2, 4]
    [5, 1, 3, 6, 4, 2]
    [5, 1, 6, 2, 3, 4]
    [5, 1, 6, 3, 2, 4]
    [5, 1, 6, 3, 4, 2]
    [5, 3, 1, 2, 4, 6]
    [5, 3, 1, 2, 6, 4]
    [5, 3, 1, 4, 2, 6]
    [5, 3, 1, 4, 6, 2]
    [5, 3, 1, 6, 2, 4]
    [5, 3, 1, 6, 4, 2]
    [5, 3, 4, 1, 2, 6]
    [5, 3, 4, 1, 6, 2]
    [5, 3, 4, 6, 1, 2]
    [5, 3, 6, 1, 2, 4]
    [5, 3, 6, 1, 4, 2]
    [5, 3, 6, 4, 1, 2]
    [5, 6, 1, 2, 3, 4]
    [5, 6, 1, 3, 2, 4]
    [5, 6, 1, 3, 4, 2]
    [5, 6, 3, 1, 2, 4]
    [5, 6, 3, 1, 4, 2]
    [5, 6, 3, 4, 1, 2]

правила

  • Стандартные лазейки запрещены (дух)
  • Входные данные могут быть приняты в любом приемлемом формате, например, список списков, список списков vararg, списки параметров и т. Д., При условии, что это однозначно, когда списки начинаются и заканчиваются.
  • Вывод может быть в любом разумном формате, при условии, что ясно, где списки начинаются и заканчиваются. Допустимые результаты включают, но не ограничиваются:
    • стандартный вывод, с одним списком на строку
    • Список списков
    • Итератор над списками (может быть реализован с помощью генератора, если они есть в вашем языке)
  • Порядок получаемых чередований не имеет значения, однако повторных чередований быть не должно.
  • Чтобы упростить повторное обнаружение, вы можете предположить, что все элементы во всех входных последовательностях являются уникальными.
  • Если в качестве входных данных не указаны списки, пустой список и выходные данные не являются действительными выходными данными.
  • Типы элементов в последовательностях не имеют значения. (например, все они могут быть одного типа или путаницы типов, в зависимости от того, что более удобно на вашем языке)
  • Ваша программа / функция должна быть гарантированно завершена за конечное время.
  • Это код-гольф , поэтому выигрывает самый короткий код для каждого языка.
code-golf sequence Beefster
источник
Единственное чередование без списков - это пустой список. Означает ли это, что мы должны выводить [[]]вместо того, []когда нам не дают списки в качестве входных данных?
Эрик Outgolfer
Кроме того, списки будут иметь одинаковую длину?
Эрик Outgolfer
Я полагаю, было бы математически разумно не возвращать списки в качестве выходных данных, если в качестве входных данных не указаны списки. Я позволю оба. Все выходные списки будут одинаковой длины. Входные списки могут различаться по длине.
Beefster

Ответы:

5

Python 2 , 103 92 79 78 байт

def f(A,c=[]):
 if not[f([b[b==x:]for b in A],c+x[:1])for x in A if x]:print c

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

Или:

Python 3 , 73 байта

def f(A,c=[]):[f([b[b==x:]for b in A],c+x[:1])for x in A if x]or print(c)

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

-1 путем замены [x[0]]с x[:1]в соответствии с XNOR

-13 байт, бесстыдно крадя, расширяясь, [b[b==x:]for b in A]как подсказывает ответ Нейла, вместо более длительного enumerateподхода.

Принимает список списков в Aкачестве входных данных. Если все элементы Aпустые, то список, оцениваемый в, ifбудет пустым, поэтому мы достигли конца рекурсии и можем print. В противном случае у нас есть список из одного или нескольких None; и мы возвращаемся.

Час Браун
источник
[x[0]]этоx[:1]
xnor
@xnor: конечно! Спасибо!
Час Браун
4

Желе , 11 байт

FŒ!fЀ⁼ṛɗÐf

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

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

FŒ!fЀ⁼ṛɗÐf  Main link. Argument: A (array of arrays)

F            Flatten A.
 Œ!          Take all permutations.
        ɗÐf  Filter by the chain to the left, keeping only permutations for which
             it returns a truthy value.
   fЀ         Intersect the permutation with each array in A.
      ⁼ṛ       Test if the result is equal to A.
Деннис
источник
3

Рубин, 66 байт

f=->a,*p{(a-=[[]])[0]?a.flat_map{|b|h,*t=b;f[a-[b]+[t],*p,h]}:[p]}

Если нет непустых последовательностей, вернуть пустую последовательность. В противном случае для каждой непустой последовательности выполните рекурсивный анализ с удаленным первым элементом, а затем добавьте его в начало каждого результата. В реализации используется допущение, что элементы гарантированно будут глобально уникальными, иначе a-[b]потенциально можно удалить более 1 последовательности из рекурсивного вызова. Хотя, если подумать, возможно, это было бы правильное поведение, чтобы избежать дублирования вывода.

Пример IO:

f[[[1,2],[3,4]]] => [[1, 3, 2, 4], [1, 3, 4, 2], [1, 2, 3, 4], [3, 1, 4, 2], [3, 1, 2, 4], [3, 4, 1, 2]]

histocrat
источник
2

Wolfram Language (Mathematica) , 76 75 71 байт

Cases[Permutations[Join@@#],x_/;And@@OrderedQ/@(x~Position~#&/@#&/@#)]&
(* or *)
Cases[Join/*Permutations@@#,x_/;And@@(x~Position~#&/@#&/*OrderedQ/@#)]&

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

Наивный подход: найти все перестановки, которые являются перемежениями ввода.

объяснение

Permutations[Join@@#]

Сгладьте <input>и найдите все его перестановки.

Cases[ ... ,x_/; ...]

Найти все элементы xтакие, что ...

(x~Position~#&/@#&/@#)

Замените все элементы в глубине 2 из <input>их соответствующей позиции в x.

And@@OrderedQ/@ ...

Проверьте, все ли списки глубины 1 упорядочены (т.е. в порядке возрастания).

Фактическая реализация чередования, 117 байт

Cases[{}~(f=ReplaceList[#2,{{a___,{b_,c___},d___}/;b>0:>#~Join~{b}~f~{a,{c},d},_:>#}]&)~#,{___},{Tr[1^(Join@@#)]+1}]&

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

Юнг Хван Мин
источник
2

Python 2 , 87 84 байта

f=lambda a:any(a)and[b[:1]+c for b in a if b for c in f([c[c==b:]for c in a])]or[[]]

Попробуйте онлайн! Порт моего JavaScript ответа. Изменить: Сохранено 3 байта благодаря @ChasBrown.

Нил
источник
-3 путем замены sum(a,[])на any(a).
Час Браун
@ChasBrown Спасибо, я не очень хорошо знаю Python.
Нил
Нейл: Ну, я думаю :). sum(a,[])имеет хорошее применение в некоторых ситуациях!
Час Браун
2

Haskell , 45 байт

f l=max[[]][h:y|h:t<-l,y<-f$t:filter(/=h:t)l]

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

Адаптировано из Chas Brown's Python answer .

Это max[[]]трюк, чтобы дать базовый случай, [[]]когда вход содержит только []элементы. В этом случае список используется для пустых, рекурсивных пуст и max[[]][]дает [[]].

При повторении, вместо выборочного удаления первого элемента выбранного списка h:t, мы создаем новый список с tфронтом и h:tотфильтровываем.

XNOR
источник
0

JavaScript (Firefox 30-57), 92 байта

f=a=>a.some(b=>b+b)?[for(b of a)if(b+b)for(c of f(a.map(c=>c.slice(c==b))))[b[0],...c]]:[[]]
Нил
источник
0

Japt -Q , 14 байт

c á f@e_XfZ eZ
c              // Flatten the input into a single array
  á            // and find all permutations.
    f          // Then filter the results for items
     @e_       // where for each original input
        XfZ eZ // the ordering of the items is unchanged.

Принимает ввод в виде массива массивов. -Qделает вывод сохранить запись массива.

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

гнида
источник
0

Scala: (не предназначен быть минимальным, более четким справочным ресурсом)

object Interleave {

  private def interleavePair[A](x: Seq[A], y: Seq[A]): Seq[Seq[A]] =
    (x, y) match {
      case (a +: c, b +: d) =>
        interleavePair(x, d).map(b +: _) ++ interleavePair(c, y).map(a +: _)
      case _ => Seq(x ++ y)
    }

  def interleave[A](ssa: Seq[Seq[A]]): Seq[Seq[A]] =
    ssa.foldLeft[Seq[Seq[A]]](Seq(Seq.empty)) {
      case (sssat, sa) => sssat.flatMap(interleavePair(sa, _))
    }
}

object Main extends App {

  import Interleave._

  println(interleave(Seq()))
  println(interleave(Seq(Seq(1, 2), Seq(3, 4))))
}

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

сатьяграху
источник
1
Вы должны хотя бы попытаться
сыграть