Змяшаць твор двух спісаў

Я хачу зрабіць наступнае: У мяне ёсць два спісу {a_1, ... a_n}, {b_1, ..., b_n} , і я хацеў бы зараз будаваць усё ператасоўкі з гэтага. Гэта азначае, што ўсе прафсаюзы гэтых спісаў у той жа час захоўваючы індывідуальны парадак бацькоўскіх спісаў.

прыклад

{a,b}, {c,d}
<�Р> {{C, D, A, B}, {C, A, D, B}, {C, A, B, D}, {а, с, д, Ь}, {а, з, Ь , в}, {а, бы, у, г}} </р>

Ці ёсць просты спосаб зрабіць гэта?

20
Сяброўская памочнік, я рады, што вам падабаецца мой адказ, але я заўсёды рэкамендую пачакаць 24 гадзіны, перш чым прыняць адказ, каб усе вакол свету ёсць шанец адказаць. Вы можаце, як і іншыя адказы лепш, калі вы дасце ім шанец здарыцца. :-)
дададзена аўтар ricree, крыніца
Добра, я буду чакаць :)
дададзена аўтар Epaga, крыніца

8 адказы

Рэкурсія

Гэта код верхняга ўзроўню, і таму наўрад ці будуць гэтак жа эфектыўным, як скампіляваць рашэнне, але рэкурсіўны алгарытм павінен мець дастатковую вылічальную складанасць:

f[u : {a_, x___}, v : {b_, y___}, c___] := f[{x}, v, c, a] ~Join~ f[u, {y}, c, b]

f[{x___}, {y___}, c___] := {{c, x, y}}  (* rule for empty-set termination *)

зараз:

f[{a, b}, {c, d}]
<�Папярэдне> {{а, бы, у, г}, {а, з, б, г}, {а, с, д, Ь}, {з, а, бы, г}, {з, а, д, Ь}, {C, d, A, B}}

доказ выніку

Было пастаўлена пытанне пра дакладнасць выніку гэтай функцыі. Вы можаце наглядна прадэманстраваць, што гэтая функцыя дае правільны вынік (як я разумею) для даўжыні 2,4 спісаў з гэтым:

ArrayPlot @ f[{Pink, Red}, {1, 2, 3, 4}]

enter image description here

  • Ружовы заўсёды папярэднічае чырвоны
  • Шэрыя значэння заўсёды будуць у парадку
  • Ці не змешвае не хапае
  • Ці не змешвае ня дублююцца

Я павінен зрабіць выснову пра тое, што спасылка папера з памылкі, ці арыгінальны пытанне разыходзіцца з вызначэння «ператасаваць прадукта» ў ім.


Пашырэнне некалькіх спісаў

While it is possible to extend a two-list shuffle product to multiple lists using Fold it may be of interest to do it directly. This code is slow however and should not be used where performance matters.

f2[in_, out___] :=
 Join @@ ReplaceList[in, {x___, {a_, b___}, y___} :> f2[{x, {b}, y}, out, a]]

f2[{{} ..}, out__] := {{out}}

f2[{{1, 2}, {Cyan}, {LightRed, Pink, Red}}]//Transpose//ArrayPlot

enter image description here


альтэрнатыўны метад

Edit: I had a function g which used Permutations on a binary list to generate all the base orderings, but I did not fill these orderings efficiently. rasher used the same start but came up with a clever and fast way to fill those orderings. I am replacing this section of my answer with a refactored version of his code; credit to him for making the Permutations approach competitive. (If you are interested in my original, slow g see the edit history.)

Вось рэфактарынг Rasher ў shufflem функцыі; Я буду называць маё shuffleW .

Edit 2017: Now significantly faster after moving or eliminating several Transpose operations.

shuffleW[s1_, s2_] := 
  Module[{p, tp, ord},
    p = Permutations @ Join[1 & /@ s1, 0 & /@ s2]\[Transpose];
    tp = BitXor[p, 1];
    ord = Accumulate[p] p + (Accumulate[tp] + Length[s1]) tp;
    Outer[Part, {Join[s1, s2]}, ord, 1][[1]]\[Transpose]
  ]

shuffleW[{a, b}, {c, d}]
<�Папярэдне> {{а, бы, у, г}, {а, з, б, г}, {а, с, д, Ь}, {з, а, бы, г}, {з, а, д, Ь}, {C, d, A, B}}

затрымкі

затрымкі of these functions as well as Simon's shuffles and rasher's shufflem, performed in v10.1.

Я таксама ўключаю неназваную, але вельмі хуткі перадапошні Rasher ў Заказ метад. Я буду называць яго shuffleO і адфарматаваць яго для зручнасці чытання.

shuffleO[s1_, s2_] :=
  With[{all = Join[s1, s2]},
    Join[1 & /@ s1, 0 & /@ s2]
     //Permutations
     //Map[Ordering @ Ordering @ # &]
     //Flatten
     //all[[#]] &
     //Partition[#, Length[all]] &
  ]

s1 = CharacterRange["a", "k"];
s2 = Range @ 11;

f[s1, s2]       //Length//RepeatedTiming
shuffles[s1, s2]//Length//RepeatedTiming
shufflem[s1, s2]//Length//RepeatedTiming
shuffleO[s1, s2]//Length//RepeatedTiming
shuffleW[s1, s2]//Length//RepeatedTiming
<�Папярэдне> {2,6523, 705432} {2,0618, 705432} {1,455, 705432} {0.78, 705432} {0,759, 705432}

Метады Rasher з'яўляюцца самымі хуткімі ў гэтым цесцю. Я лічу, мой е найбольш чытаным як механізм яго дзеяння непасрэдна відаць. Выбірай. :-)

Разрозненыя даўжыні спісу

Yi Wang posted a nice clean method that has some interesting properties. Specifically it is the best performing solution so far in the case of input lists of significantly disparate length, but they must be fed in the correct order or the performance is magnitudes worse. First in the symmetric test above:

Fold[insertElem, {{s2, 0}}, s1][[All, 1]]//Length//RepeatedTiming
<�Папярэдне> {2,67, 705432}

Зараз з разрозненымі спісаў:

s1 = Range[80];
s2 = {"a", "b", "c"};

Fold[insertElem, {{s2, 0}}, s1][[All, 1]]//Length//RepeatedTiming
<�Папярэдне> {6,25, 91881}

Памяняйце спісы і паспрабуйце яшчэ раз (так што insertElem складзеная па-над кароткага спісу):

{s2, s1} = {s1, s2};

Fold[insertElem, {{s2, 0}}, s1][[All, 1]]//Length//RepeatedTiming
<�Папярэдне> {0,121, 91881}

Гэта значна хутчэй, чым усе астатнія (парадак не мае вялікага значэння для іх):

f[s1, s2]       //Length//RepeatedTiming
shuffles[s1, s2]//Length//RepeatedTiming
shufflem[s1, s2]//Length//RepeatedTiming
shuffleO[s1, s2]//Length//RepeatedTiming
shuffleW[s1, s2]//Length//RepeatedTiming
<�Папярэдне> {0,529, 91881} {0,5637,} 91881 {0,562 91 881} {0,4135,} 91881 {0,4356,} 91881
22
дададзена
@Afriendlyhelper Калі ласка, глядзіце мой абноўлены адказ.
дададзена аўтар ricree, крыніца
@Afriendlyhelper Я не магу сказаць ад вашага заявы, чаму вы лічыце, што «ён павінен даць» выхад правільна. Не маглі б вы змяніць сваё пытанне, каб апісаць гэта?
дададзена аўтар ricree, крыніца
@Afriendlyhelper Дазвольце мне паглядзець на гэта.
дададзена аўтар ricree, крыніца
@rasher Гэта на самай справе вельмі добрае выкарыстанне спарадкаванасці і я крыху раздражнёны, я нават не думаю, каб праверыць яго тут.
дададзена аўтар ricree, крыніца
@rasher Заказ ня недаацэньваюць ад мяне, але я проста не думаю, каб выкарыстоўваць яго тут. Як хутка гэты код на вашай сістэме? У v7 гэта павольней, чым любы з ператасоўкі * функцыі, але трохі хутчэй, чым F .
дададзена аўтар ricree, крыніца
@Simon Добры момант. Паспрабую яшчэ рэфактарынг заўтра, калі б я не перайшоў на нешта іншае, або калі хтосьці не апублікаваў яшчэ больш хуткі метад да таго часу. :-)
дададзена аўтар ricree, крыніца
@Simon Дзякуй. Вы ведаеце, я цаню ваша меркаванне. Я думаю, што е добрая вітрына Mathematica сінтаксіс шаблону. (Я не хацеў бы, каб напісаць, што ў Visual Basic. Лол)
дададзена аўтар ricree, крыніца
@rasher Дзякуй за добрыя словы. Дарэчы, вы, аказваецца, даволі актывам на гэтым сайце. Рады, што ты тут. :-)
дададзена аўтар ricree, крыніца
@Afriendlyhelper Дзякуй (зноў) для Accept. Я ўпэўнены, што чакае таго каштавала, аднак, так як зараз у вас таксама ёсць метад, які ў два разы хутчэй павінен вам гэта трэба.
дададзена аўтар ricree, крыніца
@rasher Гэта выглядае вельмі цікава. Я працую на іншую пасаду, але я пабягу таймінгі трохі пазней. (Калі я забуду, торкніце мяне.) Я бачу тваё таксама заснаваны на Перастаноўкі бінарнага спісу; Я не быў задаволены тым, як я запоўніў у гэтых значэннях. Я спадзяюся, што вы працавалі трохі магіі! :-)
дададзена аўтар ricree, крыніца
Вельмі прыемна, што гэта тое, што я меў на ўвазе. Дзякуй!
дададзена аўтар Epaga, крыніца
Я глядзеў на матэматыках тэзіс аб некалькіх значэннях дзета і ён заяўляе ператасоўкі мноства {0,1} і {0,0,1,1}, згаданыя вышэй, і вынік. Глядзіце стар 11 тут math.unice.fr/~ Бруноў/GDT/& hellip; Тады я хацеў бы прайграць гэта ўручную і код і выявіў нязгоду паміж імі :(
дададзена аўтар Epaga, крыніца
@ Mr.Wizard> фіксаваны. Дзякуючы.
дададзена аўтар Epaga, крыніца
Я думаю, што я знайшоў памылку ці нешта. Выкажам здагадку, я хачу, каб ператасаваць {0,1} і {0,0,1,1}. Гэта павінна даць (010011) + 3 (001011) + 9 (000111) + (001101), але замест гэтага яна дае 9 {0, 0, 0, 1, 1, 1} + 4 {0, 0, 1, 0, 1 , 1} + {0, 0, 1, 1, 0, 1} + {0, 1, 0, 0, 1, 1}
дададзена аўтар Epaga, крыніца
@ Mr.Wizard: мае прабачэнні - там сапраўды памылка ў працы :( Давайце вінаваціць яго ў маю адсутнасць сну не бачачы яго ... Дзякуй!
дададзена аўтар Epaga, крыніца
Я выбраў гэты, так як, - як заявіў г-н Майстар і я згодны - механізм яго дзеяння непасрэдна відаць. Мне не патрэбна прадукцыйнасць у гэты момант так шмат :)
дададзена аўтар Epaga, крыніца
Я аддаю перавагу ваш метад таксама :-)
дададзена аўтар Simon Woods, крыніца
У маёй сістэме ваш рэфактарынгу кода Rasher з'яўляецца хутчэй, чым яго арыгінал, але я лічу, што мой Звесці & Partition прапанова хутчэй, чым вонкавы.
дададзена аўтар Simon Woods, крыніца
Акрамя таго, ваш код памнажае ф двойчы, гэта (ледзь-ледзь) хутчэй, каб узяць Часы з ACCF і выкарыстоўваць ФАКК [р] р у Ord
дададзена аўтар Simon Woods, крыніца
@ Mr.Wizard: Так, я пачухаў бараду крыху на гэтым! Я ўпэўнены, што ёсць яшчэ нешта засталося ў ім, быў задаволены першапачатковай вынікамі - і, вядома ж, яна распаўсюджваецца на больш чым двух спісаў <�я> справядліва </я> лёгка, я думаю. Паглядзіце наперад да вынікаў!
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: Цікаўны, што мая сапраўдная запіс робіць у вашай асяроддзі ...
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: Дзякуй, што знайшлі час. Ці будзе дадаць тлумачэнне да майго OP (пасля таго, як я хапаю іншую цыгару, ->). Акрамя таго, хацеў сказаць, у першым каментары, ваш першы вынік рэч прыгажосці - Я толькі што прачытаў гэта гэты AM (я хацеў бы паспрабаваць свае сілы, перш чым чытаць эксперт ...).
дададзена аўтар leoOrion, крыніца
@Afriendlyhelper: Я абраў бы тое ж самае, і дзякуй за самую цікавую галаваломку!
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: Праверце новы метад у маім пасьце з дапамогай ўсемагутнага, недаацэньваюць Заказ . Я быў здзіўлены яго хуткасцю.
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: Так, як я ўжо сказаў у каментарах, хутчэй, чым я думаў, што гэта будзе, але не гарачы стрыжань, каля 30% больш павольна, чым R/W/shufflers S, хоць гэта дзіўна змяняецца ў залежнасці ад пэўнай даўжынёй спісу. Я проста падумаў, што гэта пацешнае выкарыстанне Заказ .
дададзена аўтар leoOrion, крыніца
Каханне shuffleW, гэта было супер-расчараванне (у добрым сэнсе), каб думаць пра тое ж растворы, у той час як па дарозе дадому, а затым, каб зразумець, што вы рэалізавалі яго. Цікава, калі кампіляцыя можа паскорыць яе часткі.
дададзена аўтар lee smite, крыніца

Магчыма, не занадта дрэнны прадукцыйнасці мудры, не правяраў, хоць:

x = {a, b};
y = {c, d};

n = Length[x] + Length[y];
px = Subsets[Range[n], {Length[x]}];
py = Reverse[Subsets[Range[n], {Length[y]}]];

Normal /@ MapThread[SparseArray[{#1 -> x, #2 -> y}] &, {px, py}]

(* {{a, b, c, d}, {a, c, b, d}, {a, c, d, b}, {c, a, b, d}, {c, a, d, b}, {c, d, a, b}} *)

<�Моцны> Абнаўленне

Гэта мае лепшую прадукцыйнасць:

shuffles[x_, y_] := Module[{n, px, py, z, xy},
    n = Length /@ {x, y};
    {px, py} = Subsets[Range @ Tr @ n, {#}] & /@ n;
    py = Reverse @ py;
    xy = z = Join[x, y];
    (z[[#]] = xy; z) & /@ Join[px, py, 2]
  ]

shuffles[{a, b}, {c, d}]
(* {{a, b, c, d}, {a, c, b, d}, {a, c, d, b}, {c, a, b, d}, {c, a, d, b}, {c, d, a, b}} *)

<�Моцны> Tweaking іншых людзей код

Гэта рэфактарынгу рэфактарынгу г Чараўніка кода Rasher ст. Першасныя змены павінны Звесці матрыца ўпарадкаванне, так што ўвесь выхад экстрагируют з дапамогай аднаго Частка выкліку (і пасля размяркоўвалі), і паменшыць колькасць Транспанаванне аперацыі. На маім кампутары гэта дае аб павелічэнні хуткасці на 30% у параўнанні з версіяй г Чараўніка:

shuffleSWR[s1_, s2_] := Module[{p, tp, accf, ord, ss},
  p = Transpose @ Permutations @ Join[1 & /@ s1, 0 & /@ s2];
  tp = BitXor[p, 1];
  ord = Accumulate[p] p + (Accumulate[tp] + Length[s1]) tp;
  ss = Join[s1, s2];
  ss[[Flatten @ Transpose @ ord]] ~Partition~ Length[ss]]
15
дададзена
Я перапрацаваны змешвае . Калі вам не падабаецца, змены проста вярнуць яго.
дададзена аўтар ricree, крыніца

Нешта іншае, непрактычна яшчэ пацешнае, з намёкам матэматычнай бесклапотнасці ...

s1 = {a, b, c}
s2 = {f, g, h}

sall = Join[s1, s2];
ln = Length[sall];

s = Solve[
   Max[sall] == ln && Min[sall] == 1 && Less[Sequence @@ s1] && 
    Less[Sequence @@ s2] && Unequal[Sequence @@ sall], sall, Integers];

[email protected] /. MapAt[Reverse, s, {All, All}]

І для майго фактычнага пранікнення ў скоках, я прапаную наступнае. Здаецца, каб пабіць цяперашні рэкардсмен даволі зручным у маіх абмежаваных выпрабаваннях.

shufflem[s1_, s2_] := Module[{ss, sr, s1l, s2l, p, pp, tp, pres},

  {ss, sr} = {Join[s1, s2], [email protected]((s1l = [email protected]) + (s2l = [email protected]))};

  p = Permutations[Join[ConstantArray[1, s1l], ConstantArray[0, s2l]]];

  pp = ([email protected][p]//Transpose) p;

  tp = Clip[p, {1, 0}, {1, 0}];

  pres = pp + 
    Clip[([email protected][tp]//Transpose) tp + s1l, {s1l + 1, Max[sr]}, {0, 0}];

  ss[[#]] & /@ pres
  ]

Па просьбе г-майстар, тлумачэнне для чытачоў.

Абдумваючы гэта за абедам, я ўяўляў яго ў якасці аднаго са спісу «булькатанне» праз іншы. Шаблон, які прыйшло на розум быў відавочны: двайковы лічыльнік роду рэчы, дзе 1 і 0 ўяўляюць пазіцыі ў ператасаваў спіс.

Маючы розныя значэнні робіць аперацыю перастаноўкі разумным, то ёсць, проста наіўна перастановай уся «калода» спісаў і фільтрацыі вынікаў у асноўным марна працы, так як большасць з іх будзе мець элементы, якія парушаюць правілы парадку, у той час як якія маюць толькі прадстаўлення <�ет> некаторы элемент у некаторыя спіс азначае, што мы ніколі не ўбачым такіх транспазіцыя у перастанове.

Маючы гэта на ўвазе, я стварыць спіс магчымых пазіцый у спісе змешваюцца (дыяпазон агульнай даўжыні ў сцёр), разам з робячы аб'яднаную версію спісаў (сс).

Я затым пабудаваць (у р) спіс з 1 і 0, у колькасцях, адпаведных даўжыні кожнага зыходнага спісу, і генераваць перастаноўкі. Так што цяпер у мяне ёсць вялікі спіс усіх магчымых перастановак канчатковага ператасаваў спіс, з 1, дзе элементам з першага спісу ідзе, і ў 0 для тых, хто з другога.

Мы хочам, каб элементы, каб запоўніць гэтыя 1/0 слотаў быць у парадку арыгіналаў, то ёсць элемент 1,2,3 ... для кожнага.

Таму я акумуляваць над кожнай перастановай (я двойчы транспонировать для выканання), пакінуўшы мяне нешта накшталт {1,0,1,1,0,0} будуць {1,1,2,3,3,3}. Я зацікаўлены толькі ў дэталях з першага спісу на першым праходзе, так Я памнажаць accumulants іх адпаведнай перастаноўкай, напрыклад, у дадзеным прыкладзе мы атрымаем {1,0,2,3,0,0} для гэтага адной перастаноўкі, гэта значыць з першага спісу, слоты 1,3 і 4 запаўняюцца з 1,2 спісу элементаў і 3 далучыўся спіс.

The second pass fills the 0 spots from the second list, by doing the same thing with some hand-waving to get the values into the second half of the joined list: I clip the permutations to turn 1->0 and 0->1, do the same machination as the last, but I add an offset (the length of the first list prefix in the joined list). I clip out noise values, ending up with the list of permutations with elements looking like {1,4,2,3,5,6}, etc.

Нарэшце, я карта над гэтым вынікам спісаў перастановак індэксацыі іх у злучаным спіс, так, напрыклад, калі далучыўся спіс быў {а, бы, у, г, д, е}, элемент прыкладу перастаноўкі можа прывесці да {а, д, бы, у, д, е} цягне.

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

І, нарэшце, на здзіўленне хутка (я думаў, што гэта будзе значна больш павольна, чым гэта аказваецца) метад, які дазваляе пазбегнуць якіх-небудзь матэматычных маніпуляцый:

Module[{jl = Flatten[{#1, #2}]},
   Partition[
    jl[[Flatten[
       Ordering /@ 
        Ordering /@ 
         Permutations[
          Join[ConstantArray[1, Length[#1]], 
           ConstantArray[0, Length[#2]]]]]]], Length[jl]]] &[s1, s2]

І гэта выкарыстанне спарадкаванасці яшчэ хутчэй з-за адносна невялікага памеру ўваходных спісаў, аказваецца адлюстраванне над імі хутчэй, у выніку чаго агульнага часу, здаецца, канкураваць з рэарганізаванай * рэарганізаванай версіяй майго арыгінала. цікава:

Partition[ Join[#1, #2][[Flatten[ Ordering[Ordering[#]] & /@ 
       Permutations[Flatten[{1 & /@ #1, 0 & /@ #2}]]]]],
   Length[#1] + Length[#2]] &[s1, s2]

І, нарэшце, паказаны вышэй абагульнены, каб больш спісаў (таймінгі на нетбуке, які быў побач з разрыўнымі полымем):

lists = {{a, b, c, d}, {e, f, g, h, i}, {j, k, l, m, n, o}}

res2 = Partition[ Flatten[##][[Flatten[ Ordering[Ordering[#]] & /@ 
          Permutations[Flatten[MapIndexed[(idx = #2[[1]]; idx & /@ #1) &, ##]]]]]],
      Length[Flatten[##]]] &[lists];//Timing

Length[res2]

res2//Short

(* {4.539629, Null} *)

(* 630630 *)

(* {{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o},{a,b,c,d,e,f,g,h,j,i,k,l,m,n,o},<<630627>>,{j,k,l,m,n,o,e,f,g,h,i,a,b,c,d}} *)

Любы з спосабаў стаць даволі бескарысным з вялікімі спісамі і/або вялікай колькасцю спісаў:

enter image description here

напрыклад, два спісу з 40 элементаў, быў адзін у стане зрабіць перастаноўкі, якія прыліпаюць да правіла упарадкавання з хуткасцю 1,000,0000 у секунду будзе значна перавышаць ўзрост Сусвету да завяршэння.

Ніжэй генеруе выпадковую перастаноўку, якая прыліпае да правіл упарадкавання для такіх выпадкаў:

randomOrderedShuffle[lists__] := 
 Join[lists][[[email protected]@[email protected](Join @@ ConstantArray @@@ 
         Transpose[{[email protected]@{lists}, Length /@ {lists}}])]]

(* The following example has 3,644,153,415,887,633,116,359,073,848,179,365,185,734,400  "valid" permutations... *)

randomOrderedShuffle[Range[10], Range[11, 20], Range[21, 30], Range[31, 40], Range[41, 50], Range[51, 60]]//Timing

(*  {0., {1, 21, 41, 11, 22, 12, 31, 23, 51, 2, 3, 52, 42, 13, 14, 53, 43, 15, 32, 4, 54, 16, 33, 17, 34, 55, 5, 44, 45, 56, 6, 35, 57, 36, 7, 46, 8, 37, 58, 24, 59, 47, 25, 9, 10, 60, 26, 48, 18, 27, 19, 38, 49, 28, 39, 29, 40, 30, 20, 50}}  *)
13
дададзена
@SimonWoods На маёй сістэме гэта здаецца, што маё выкарыстанне Outer гэта тое ж самае хутка; Вы можаце пацвердзіць, што для пазнейшых версій?
дададзена аўтар ricree, крыніца
@rasher Ваш апошні, не абагульнены код займае 2 секунды ў v7 на маім сіметрычным цесцю. Тым не менш, я люблю гэта.
дададзена аўтар ricree, крыніца
Я хачу, каб пераканацца, што я разумею, адзін з вашых заяў; Вы можаце пацвердзіць, што ў v9 другой лініі хутчэй, чым першы?: <�Код> Заказ/@ заказу/@ падстановак [Range @ 9]//Timing//Першая супраць Заказ [Заказ [# ]] &/@ падстановак [Range @ 9]//Timing//Першая . У v7 яны эквівалентныя.
дададзена аўтар ricree, крыніца
Я люблю бачыць вас прыняць гэты «просты» пытанне да гэтага часу. Я галасаваў бы зноў, калі б мог. Дарэчы, у вышэйшай ступені рэкурсіі ( F ) мае перавагу ў тым, што кожная галіна можа быць перапынена і працягвалі па меры неабходнасці, у той час як рашэнні, выкарыстоўваючы Перастаноўкі , у канчатковым рахунку вычарпаць памяць.
дададзена аўтар ricree, крыніца
:) ... ён працуе толькі з неинициализированными зменнымі, хоць.
дададзена аўтар Marcel, крыніца
Гэта падыход, які я хацеў узяць, але я не мог бачыць хуткі спосаб вылічэння Pres . <�Код> назапашваліся трук вельмі разумны. Выдатная праца!
дададзена аўтар Simon Woods, крыніца
Што да апошняга пункта, што Карта гэта самая павольная частка, вы можаце зэканоміць час, выканаўшы SS [[Звесці @ вр]] ~ Partition ~ Даўжыня [сс] замест
дададзена аўтар Simon Woods, крыніца
@ Mr.Wizard: Цікаўны, што апошняе рэдагаванне робіць у тэстах: здаецца, так хутка, як самы хуткі рэфактарынгу метад назапашвання ў маіх абмежаваных выпрабаваннях, і прыгажэе ИМО ...
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: LOL, я не павінен вам сказаць, што гэта адна з тых нетрывіяльных «трывіяльных» пытанняў! Так, ёсць шмат разоў прыгажосць вашага рэкурсіўнага рашэння - шмат чаму навучыліся ісці па ёй.
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: так, на маім цацачным тэставанні, другі паслядоўна на 10-20% хутчэй. Акрамя таго, у маіх тэстах, ня-абагульненая версія апошняй з'яўляецца шыя ў ноздру з КСВ рэфактарынгу майго ОП. І, нарэшце, я трохі збянтэжаны таймінгі на абагульненай версіі - гэта паслядоўна 20% больш павольна, чым іншыя з тымі ж аргументамі. Як быццам перадаючы ## замест спасылак на розныя аргументы робіць розніцу. Гэта смяхотная гадзіну тут, так прэч, каб мяшок, але я буду тыкаць у гэтым.
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: Дзякуй, што знайшлі час, каб праверыць у вашай асяроддзі!
дададзена аўтар leoOrion, крыніца
@ Mr.Wizard: Уздоўж лініі, што я/быў тонкай налады. Ёсць некаторыя іншыя ідэі, але цыгары ў вусны гарэння стадыі, час ударыць мех. Мне цікава, што раніца прынясе ;-). Які вялікае пытанне і мноства адказаў!
дададзена аўтар leoOrion, крыніца
@SimonWoods: Шануеце каментар! Так, як я пракаментаваў Mr.W, я драпаў вакол трохі на гэтым. Я думаю, што ёсць больш тонкая налада ;-)
дададзена аўтар leoOrion, крыніца
Так, ён быў задуманы як лох. Даданне майго рэальную запісу зараз ...
дададзена аўтар leoOrion, крыніца

Як наконт ўстаўкі першага спісу ў другой спіс у кожнай дазволенай пазіцыі (дзе гэта дазволена сродак, якое захоўвае парадак першага спісу)?

lst1 = {a, b};
lst2 = {c, d};

insertElem[lst_, x_] := 
  Join @@ (Table[{Insert[#, x, i], i}, {i, #2 + 1, [email protected]# + 1}] & @@@ lst)

Fold[insertElem, {{lst2, 0}}, lst1][[All, 1]]
<�Папярэдне> {{а, бы, у, г}, {а, з, б, г}, {а, с, д, Ь}, {з, а, бы, г}, {з, а, д, Ь}, {C, d, A, B}}

Мне сказалі, каб не выкарыстоўваць павольную Insert. Але тут генерацыі перастановак значна складаней. Такім чынам Устаўка можа быць не так ужо дрэнна.

<�Моцны> EDIT: Яшчэ горш спроба

Гэта не так эфектыўна, як паказана вышэй. Але проста для задавальнення, можна генераваць пазіцыі lst2 ў выніку, а затым генераваць пазіцыі lst1 ~ Рэгістрацыя ~ lst2 ў выніку. Нарэшце, перастаўляюць lst1 ~ Рэгістрацыя ~ lst2 ў канчатковы вынік:

comb[lenIn_, lenOut_] := Module[{i},
  i[0] = 0;
  Flatten[#, lenOut - 1] & @ With[{
     elem = [email protected]# & /@ [email protected], 
     ranges = Sequence @@ ({i[#], i[# - 1], lenIn - 1} & /@ [email protected])}, 
    Table[elem, ranges]]]

(* e.g. comb[3,2] gives {{0, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}, {2, 2}} *)
(* One can also write comb as follows, with even worse performance *)
(* comb[lenIn_, lenOut_] := Select[Tuples[Range[0, lenIn - 1], lenOut], OrderedQ] *)

shufflep[lst1_, lst2_] := Module[{pos2, pos},
  pos2 = [email protected]@lst2 + # & /@ comb[[email protected] + 1, [email protected]];
  pos = Complement[Range[[email protected] + [email protected]], #]~Join~# & /@ pos2;
  Permute[lst1~Join~lst2, [email protected]#] & /@ pos]
11
дададзена
Гэта даволі чысты метад, і я бачу магчымасць зрабіць гэты код трохі чысцей яшчэ. Ці магу я змяніць свой пост з гэтымі зменамі? Калі вам не падабаецца іх, вы можаце проста «вярнуць» рэдагаванне, каб адмяніць іх.
дададзена аўтар ricree, крыніца
Нататкі: (1) Калі спісы, якія сабраны кароткія Уставіць ня дорага; гэта добры метад. (2) Паколькі вы Fold над lst1 , lst1 павінен быць <�я> менш з двух спісаў, калі ёсць адзін ; гэта будзе <�я> шмат </я> хутчэй, чым наадварот.
дададзена аўтар ricree, крыніца
Калі ласка, глядзіце таймінгаў я дадаў да майго адказу. У некаторых выпадках ваш метад, несумненна, самы хуткі спосаб яшчэ адказваў, пры правільным ужыванні. Добра зроблена.
дададзена аўтар ricree, крыніца
@YiWang: Вельмі прыемна. +1
дададзена аўтар leoOrion, крыніца
Вядома. Вы можаце рэдагаваць!
дададзена аўтар Fearless, крыніца
Вялікі дзякуй @ Mr.Wizard! Гэта сапраўды чысцей!
дададзена аўтар Fearless, крыніца

Зусім жудасна неэфектыўны:

l = {{a, b}, {c, d}};

Intersection @@ (Cases[Permutations[Flatten[l]],Riffle[#, ___, {1, -1, 2}]] & /@ l)
<�Р> {{а, бы, у, г}, {а, з, б, г}, {а, с, д, Ь}, {з, а, бы, г}, {з, а, г , Ь}, {C, d, A, B}} </р>

... і гэта становіцца толькі горш, увогуле выпадку з $ N $ спісаў:

l = {{a, b}, {c, d}, {e, f}};

Intersection @@ (Cases[Permutations[Flatten[l]],Riffle[#, ___, {1, -1, 2}]] & /@ l)
<�Р> {{а, бы, у, г, д, е}, {а, бы, у, д, д, е}, {а, бы, у, д, е, в}, {а, бы , е,      у, г, е}, {а, Ь, е, з, е, в}, {а, бы, д, е, з, d}, {а, з, б, д, е,     е}, {а, з, б, в, д, е}, {а, з, Ь, д, е, в}, {а, с, д, б, д, е}, {а,     у, г, е, б, е}, {а, у, г, д, е, Ь}, {а, з, е, б, г, е}, {а, з, е, б,      F, D}, {а, з, е, в, б, е}, {а, з, е, д, е, Ь}, {а, с, д, е, б,     д}, {а, с, д, е, д, Ь}, {а, е, бы, у, г, е}, {а, е, бы, у, е, в}, {а,     е, B, F, C, D}, {а, е, з, б, г, е}, {а, е, с, Ь, е, в}, {а, е, с, д,      B, F}, {а, е, с, д, е, Ь}, {а, е, з, е, б, г}, {а, е, з, е, д,     Ь}, {а, е, ё, бы, у, г}, {а, е, ё, с, б, г}, {а, е, ё, с, д, Ь}, {з,     а, бы, г, д, е}, {з, а, бы, д, д, е}, {з, а, бы, д, е, в}, {з, а, д, бы,      д, е}, {з, а, д, е, б, е}, {C, A, D, E, F, B}, {з, а, е, б, в,     е}, {з, а, е, б, е, в}, {з, а, е, в, б, е}, {з, а, е, д, е, Ь}, {з,     а, д, е, б, г}, {з, а, д, е, д, Ь}, {C, D, а, бы, д, е}, {C, D, A, E,      B, F}, {C, D, A, E, F, B}, {C, D, E, A, B, F}, {C, D, E, A, F,     Ь}, {C, D, E, F, A, B}, {з, е, а, бы, г, е}, {з, е, а, бы, е, в}, {з,     е, а, д, б, е}, {з, е, а, г, е, Ь}, {з, е, а, е, б, г}, {з, е, а, е,      д, Ь}, {з, е, д, а, бы, е}, {з, е, д, A, F, B}, {C, E, D, F, а,     Ь}, {с, д, е, а, бы, г}, {с, д, е, а, д, Ь}, {с, д, е, д, а, Ь}, {е,     а, бы, у, г, е}, {е, а, бы, у, е, в}, {е, а, бы, е, з, d}, {е, а, з, Ь,      д, е}, {е, а, з, Ь, е, в}, {е, а, з, в, б, е}, {е, а, у, г, е,     Ь}, {е, а, з, е, б, г}, {е, а, з, е, д, Ь}, {е, а, е, бы, у, г}, {е,     а, F, C, B, D}, {е, а, F, C, D, B}, {е, з, а, бы, г, е}, {е, з, а, бы,      F, D}, {е, з, а, д, б, е}, {е, з, а, г, е, Ь}, {е, з, а, е, б,     д}, {е, з, а, е, д, Ь}, {е, с, д, а, бы, е}, {е, с, д, A, F, B}, {е,     у, г, е, а, Ь}, {е, з, е, а, бы, г}, {е, з, е, а, д, Ь}, {е, з, е, д,      а, Ь}, {д, е, а, бы, у, г}, {д, е, а, з, б, г}, {д, е, а, з, д,     Ь}, {д, е, з, а, бы, г}, {д, е, з, а, д, Ь}, {E, F, C, D, A, B}} </р>
3
дададзена
@David Адносная эфектыўнасць можа быць пераацаніць, але вылічальная складанасць <�я> не . Гэта трывае няўдачу на апошнім.
дададзена аўтар ricree, крыніца
@YvesKlett LOL - Я спадзяюся, што было напісана з усмешкай на твары, як я сам сабе. :-)
дададзена аўтар ricree, крыніца
@ Mr.Wizard сапраўды: D
дададзена аўтар Marcel, крыніца
@ Mr.Wizard O (няма!)
дададзена аўтар Marcel, крыніца

Яшчэ адзін спосаб!

list1 = {a, b};
list2 = {c, d};
list = Range[2 [email protected]];
first = Select[Permutations[list, {([email protected])}], Sort[#] === # &];
second = Complement[list, #] & /@ first;
Normal[SparseArray[#]] & /@
(Join @@@ ([email protected]{Thread[Rule[#, list1]] & /@ first,Thread[Rule[#, list2]] & /@ second}))
<�Р> {{а, бы, у, г}, {а, з, б, г}, {а, с, д, Ь}, {з, а, бы, г}, {з, а, г ,     Ь}, {C, D, A, B}} </р>
2
дададзена

Я позна, каб прыбыць. Як наконт Однострочник ўзгаднення з выкарыстаннем шаблону:

Cases[Cases[Permutations[{a,b,c,d}], {___, a, ___, b, ___}], {___, c, ___, d, ___}]

Аўтаматызаваная форма:

MrShuffles[lis1_, lis2_] := Cases[ Cases[Permutations[Join[lis1, lis2]],
 Riffle[lis1, ___, {1, -1, 2}]], Riffle[lis2, ___, {1, -1, 2}]]

прыклад:

MrShuffles[{a, b}, {c, d}]
<�Р> {{а, бы, у, г}, {а, з, б, г}, {а, с, д, Ь}, {з, а, бы, г}, {з, а, г ,     Ь}, {C, D, A, B}} </р>
MrShuffles[{a, b, c}, {d, e}]
<�Р> {{а, бы, у, д, е}, {а, бы, д, з, е}, {а, бы, д, е, з}, {а, д, бы, у,     е}, {а, д, б, в, з}, {а, д, е, бы, у}, {д, а, бы, у, е}, {д, а, бы, д,     з}, {д, а, е, Ь, з}, {д, е, а, бы, у}} </р>
1
дададзена
shuffle[list1_, list2_] := 
 Module[{i = 0, len1 = Length[list1], len2 = Length[list2]}, 
  Fold[Insert[#1, list2[[Mod[++i, len2, 1]]], #2] &, list1, #] & /@ 
   Subsets[Range[len1 + len2], {len2}]]

0
дададзена
Я правяраў, каб бачыць, што гэты метад працуе належным чынам. Глядзіце маё абнаўленне meta.mathematica.stackexchange.com/a/2113/121 - вы можаце зрабіць астатняе.
дададзена аўтар ricree, крыніца
@ Mr.Wizard Ну, я трохі румян, каб убачыць вас зрабіць гэта адзін за адным, для мяне, я буду рэдагаваць тыя спасылку на малюнак у будучыні. :)
дададзена аўтар GroundZero, крыніца