Semua cara yang mungkin untuk interleave dua string

21

Saya baru-baru ini melihat pertanyaan ini di stackoverflow. Ini pertanyaan yang bagus, tetapi ada satu masalah fatal dengan pertanyaan itu. Mereka meminta cara terbaik untuk melakukannya. Misalnya, paling mudah dibaca, paling idiomatis, paling rapi, dll. Tidakkah mereka tahu itu bukan masalah? Anda seharusnya bertanya tentang bagaimana melakukannya dengan byte kode paling sedikit!

Karena saya ragu pertanyaan itu akan dihargai di stackoverflow, saya memutuskan untuk menanyakannya di sini.

Tantangan

Anda harus menulis program atau fungsi sesingkat mungkin yang menghasilkan semua cara yang memungkinkan untuk menjalin hubungan dua string sembarang. Misalnya, jika dua string adalah 'ab'dan 'cd', outputnya adalah:

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

Seperti yang Anda lihat, aselalu sebelumnya b, dan cselalu sebelumnya d.

IO dapat dalam format apa pun yang masuk akal. Gunakan kode python ini untuk memverifikasi untuk memeriksa output Anda. (kredit: JeD )

def shuffle(s,t):
    if s=="":
        return [t]
    elif t=="":
        return [s]
    else:
        leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
        rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
        leftShuffle.extend(rightShuffle)
        return leftShuffle

Sampel IO:

shuffle("$", "1234"):
['$1234', '1$234', '12$34', '123$4', '1234$']

shuffle("az", "by"):
['azby', 'abzy', 'abyz', 'bazy', 'bayz', 'byaz']

shuffle("code", "golf"):
['codegolf', 'codgeolf', 'codgoelf', 'codgolef', 'codgolfe', 'cogdeolf', 'cogdoelf',
'cogdolef', 'cogdolfe', 'cogodelf', 'cogodlef', 'cogodlfe', 'cogoldef', 'cogoldfe',
'cogolfde', 'cgodeolf', 'cgodoelf', 'cgodolef', 'cgodolfe', 'cgoodelf', 'cgoodlef',
'cgoodlfe', 'cgooldef', 'cgooldfe', 'cgoolfde', 'cgoodelf', 'cgoodlef', 'cgoodlfe',
'cgooldef', 'cgooldfe', 'cgoolfde', 'cgolodef', 'cgolodfe', 'cgolofde', 'cgolfode',
'gcodeolf', 'gcodoelf', 'gcodolef', 'gcodolfe', 'gcoodelf', 'gcoodlef', 'gcoodlfe',
'gcooldef', 'gcooldfe', 'gcoolfde', 'gcoodelf', 'gcoodlef', 'gcoodlfe', 'gcooldef',
'gcooldfe', 'gcoolfde', 'gcolodef', 'gcolodfe', 'gcolofde', 'gcolfode', 'gocodelf',
'gocodlef', 'gocodlfe', 'gocoldef', 'gocoldfe', 'gocolfde', 'goclodef', 'goclodfe',
'goclofde', 'goclfode', 'golcodef', 'golcodfe', 'golcofde', 'golcfode', 'golfcode']

Seperti biasa, celah standar berlaku, dan jawaban terpendek dalam byte akan menang. Karena pertanyaannya awalnya tentang python, saya ingin melihat jawaban python terpendek. (Dan tidak, pyth bukan python). Namun, jawaban dalam bahasa apa pun dianjurkan.

DJMcMayhem
sumber
5
Byte kode yang paling sedikit adalah cara terbaik untuk melakukannya, setiap orang tahu itu! * (Disclaimer: not CR).
Rɪᴋᴇʀ
1
Apakah semua karakter berbeda? Atau belum tentu?
aditsu
4
Sebenarnya ... dalam contoh "kode", "golf" Anda memiliki duplikat "o" dan hasil duplikat juga, misalnya 'gcoodelf'. Saya akan menganggap itu yang Anda inginkan.
aditsu
1
"Aku baru saja menemukan pertanyaan hebat ini. Namun, ada satu kesalahan fatal: mereka ingin itu dilakukan dengan baik!"
Cyoce
1
Anda harus memberikan sampel IO untuk "aabb", "bc".
Taemyr

Jawaban:

1

Pyth, 26

M?G?H++LhGgtGH+LhHgGtH]G]H

Coba di sini

Ini adalah implementasi yang sangat mendasar dari formula rekursif yang diberikan. Ini mendefinisikan fungsi gyang melakukan tugas yang diperlukan. Tautan ini adalah program yang dimodifikasi yang membaca string dari STDIN baris baru yang dipisahkan, agar lebih nyaman. Untuk memanggil fungsi lakukan g<string1><string2>.

Ekspansi:

M                ##  Define a function g taking two arguments: G and H
 ?G?H ... ]G]H   ##  Two ternaries: if G is empty return a list containing H
                 ##  if H is empty return a list containing G
   +             ##  otherwise return these next two lists joined together
   +LhGgtGH      ##  the first letter of G added to each result of a recursive call to g
                 ##  with G missing its first character and H
   +LhHgGtH      ##  the same as above but with G and H swapped

Dua panggilan rekursif sangat mirip, tetapi saya belum dapat menemukan cara untuk golf mereka lagi.

FryAmTheEggman
sumber
10

Haskell, 53 48 byte

a%""=[a]
a%b=[x:t|(x:y,z)<-[(a,b),(b,a)],t<-y%z]

Menentukan fungsi %yang a%bdengan string a,bmemberikan daftar string.

Diberikan dua string, kami memilih satu dari dua untuk mengambil karakter pertama. Kami kemudian mengulangi pada sisa dua string, mengawali karakter itu untuk setiap hasil.

Ketika salah satu string kosong, satu-satunya hasil yang mungkin adalah string lainnya. ""%""=[""]akan cukup, tapi lebih lama.


53 byte:

a@(b:c)%d@(e:f)=((b:)<$>c%d)++((e:)<$>a%f)
a%d=[a++d]

Menentukan fungsi %yang a%ddengan string a,dmemberikan daftar string.

Fungsi ini didefinisikan secara rekursif. Jika kita mengambil karakter dari string pertama, maka karakter tersebut harus diawali dengan masing-masing hasil dari panggilan rekursif pada sisa-sisa string pertama dengan string kedua. Secara simetris untuk string lainnya.

Untuk kasus dasar, jika salah satu string kosong, hasilnya adalah daftar elemen tunggal dari rangkaian mereka. Ini lebih pendek dari dua case untuk setiap string yang kosong.

Tidak
sumber
@ Aditsu Ups, maksudku ""%""=[""].
xnor
Sungguh aneh memiliki jawaban yang menang atas Anda tepat satu byte dalam bahasa yang persis sama
haskeller bangga
10

Haskell, 47

(x:s)#b=(x:)<$>s%b
a#b=[]
[]%b=[b]
a%b=a#b++b#a

% adalah operator yang memecahkan tantangan ini.

#adalah operator yang menerima dua daftar dan menemukan semua cara untuk menyisipkannya sedemikian rupa sehingga karakter pertama berasal dari string pertama (dengan casing tepi - jika daftar pertama kosong, maka hasilnya adalah daftar kosong) dengan mengulangi ke %.

lalu, %bekerja dengan hanya menerapkan #dua kali.

Sunting: Versi sebelumnya memiliki bug yang ""%""dikembalikan ["",""], jadi saya memperbaikinya. Itu diperbaiki dengan menambahkan kasus dasar ke %, yang kemudian memungkinkan untuk menghapus kasus dasar dari panjang yang sama #(yang benar-benar, tidak masuk akal).

haskeller bangga
sumber
@nimi Tapi tipe mismach - (#) :: [a]->[a]->[[a]], jadi a::[a]dan hasilnya harus tipe[[a]]
bangga haskeller
Ups, Anda benar. Maaf.
nimi
8

Python 2, 71 byte

f=lambda*p:[x[0]+t for x,y in p,p[::-1]for t in x and f(x[1:],y)]or['']

Contoh dijalankan:

>> f('ab','AB')
['abAB', 'aABb', 'aAbB', 'ABab', 'AabB', 'AaBb']

Diberikan dua string, x,ykita dapat mengambil karakter pertama xdan menambahkannya ke setiap hasil panggilan rekursif dengan hilang f(x[1:],y). Atau, kita dapat melakukan hal yang sama dengan xdan yberalih. Dengan mengambil x,yinput patau pembalikannya `p [:: - 1], kita mendapatkan kedua kemungkinan.

Untuk menghindari pengambilan dari string kosong x, kami melakukan hubungan arus pendek dengan x and. Jika kedua string kosong, string tidak dapat xdan kami mendapatkan dan mengosongkan daftar kemungkinan, yang kami perbaiki dengan orkasus dasar yang benar [''].

Strategi generatif serupa di Python 3 (73 byte):

f=lambda p,s='':[f((x[1:],y),s+x[0])for x,y in[p,p[::-1]]if x]or print(s)
Tidak
sumber
Sihir macam apakah ini?! (+1)
aditsu
3

Python, 80

Seperti yang diminta, inilah jawaban python:

f=lambda a,b,c='':[c+x for x in[a+b][a>''<b:]or f(a[1:],b,a[0])+f(a,b[1:],b[0])]

Terima kasih Sp3000 untuk makan 4 byte :)

aditsu
sumber
2

CJam, 38

q~L{_2$e&{_2$(\@jf+@@(@@jf++}{+a}?}2jp

Cobalah online

Pemrograman dinamis (menggunakan rekursi memoized).

Penjelasan:

q~         read and evaluate the input (2 strings)
L{…}2j     calculate with memoized recursion with no initial cache and 2 arguments
  _2$      copy the 2 strings
  e&{…}    if they are both non-empty
    _2$    copy the strings again (they're in reverse order)
    (      take out the first character of the first string
    \@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    @@     bring the other copy of the strings on top (in order)
    (      take out the first character of the second string
    @@     move the strings after the character
    j      solve recursively
    f+     prepend the character to all results
    +      concatenate the 2 sets of results
  {…}      else
    +      concatenate the 2 strings (at least one is empty)
    a      put the result in an array
  ?        end if
p          pretty-print the results for the input strings
aditsu
sumber
2

CJam, 32 byte

qN/_:,eeWf%e~e!\f{\{_2$=(ot}/No}

Uji di sini.

Ini terasa sangat golf, tetapi sejauh ini saya hanya menemukan 4 solusi alternatif yang semuanya memiliki jumlah byte yang sama:

qN/_ee{),*~}%e!\f{\{_2$=(ot}/No}
l_:!l_0f>@+])e!\f{\{_2$=(ot}/No}
ll__3$:!+.=])e!\f{\{_2$=(ot}/No}
qN/[_:,2,]ze~e!\f{\{_2$=(ot}/No} (found by Sp3000)

Ide dasarnya adalah untuk menghasilkan semua permutasi dari 0s dan 1s terkait dengan string mana untuk mengambil setiap karakter dalam hasil dari. Itu semuanya terserah dan termasuk e!. Sisanya hanya mengeluarkan karakter dalam urutan itu dari dua string itu.

Martin Ender
sumber
Bagus, saya memikirkan ide itu tetapi tidak berpikir bisa bermain golf dengan baik.
aditsu
@aditsu Yang benar-benar kita butuhkan adalah campuran antara e*dan .*yang mengulangi setiap elemen dengan jumlah yang berbeda. ;) (Yaitu operator yang harus dilakukan :a.*:~. Saya kira e*dapat digunakan untuk itu karena saat ini kesalahan jika diberi dua daftar.)
Martin Ender
2

JavaScript (Firefox 30-57), 88 84 81 byte

(s,t,g=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>[...g(s,t),...g(t,s)]

Sunting: Disimpan 4 byte dengan meningkatkan kondisi terminasi saya. Disimpan 3 byte berkat @ edc65.

Neil
sumber
Terlalu dekat untuk menerbitkan, tetapi lihatlah - ini lebih pendek:f=(a,b,z=(v,w)=>v[1]?f(v.slice(1),w).map(x=>v[0]+x):[v+w])=>z(a,b).concat(z(b,a))
edc65
@ edc65 Sangat bagus; Saya sudah mencoba dan gagal menggunakan vsebagai kondisinya, tetapi tidak pernah terpikir oleh saya untuk menggunakannya v[1].
Neil
2

Brachylog , 8 byte

p~cᵐz₁cc

Cobalah online!

Mengambil input sebagai daftar dua string melalui variabel input, dan menghasilkan semua interleaving yang mungkin melalui variabel output. Karena kasus pengujian tampaknya memungkinkan duplikat interleaving di mana ada surat bersama, saya belum berhati-hati untuk menghindarinya, tetapi ini menghasilkan lebih banyak duplikat dan tidak hanya dengan surat bersama. (Jika ini tidak diizinkan, tetapi duplikat surat bersama tidak diperlukan, tambahkan saja tiga byte untuk dimasukkan {}ᵘsebagai keluaran tanpa daftar duplikat.)

p           A permutation of
            the input variable
   ᵐ        with each element
 ~c         arbitrarily partitioned,
    z       zipped
     ₁      without cycling,
      cc    and concatenated twice
            is the output variable.

Pada dasarnya, ini menghasilkan setiap partisi dari kedua string, kemudian menyisipkannya dengan cara deterministik normal dalam urutan apa pun. Interleaving duplikat tambahan disebabkan oleh pasangan partisi di mana perbedaan antara panjang yang pertama dan panjang yang kedua memiliki beberapa nilai selain 0 atau 1, sehingga salah satu dari mereka memiliki potongan yang disatukan satu sama lain di akhir. Jadi, untuk menghasilkan keluaran dengan multiplisitas yang sama dengan keluaran sampel:

Brachylog , 17 byte

p~cᵐ{lᵐ-ℕ<2&}z₁cc

Cobalah online!

Kode tambahan {lᵐ-ℕ<2&},, gagal setiap pasangan partisi di mana setiap divisi asing dibuat. (Saya mengubah tajuk pada TIO untuk dicetak dengan tanda kutip untuk memudahkan keluaran memeriksa di kulit Python.)

String yang tidak terkait
sumber
1

MATL , 34 30 byte

h1Mgw~hY@Xu!ttYs*w~tYs1Gn+*+!)

Ini menggunakan ide dari jawaban ini : jika panjang string adalah mdan n, sebutkan semua m+npola mbit dengan bit yang ditetapkan. Salah satu cara melakukan itu penghitungan adalah: menghasilkan semua permutasi dari vektor dengan msatu dan nnol dan kemudian menghapus duplikat.

Cobalah online!

Penjelasan

h     % implicitly input the two strings of lengths m and n. Concatenate
1M    % push the two strings again
g     % convert the second strings into ones
w~    % swap. Convert the second string into zeros
h     % concatenate: vector of zeros and ones
Y@    % 2D array with all permutations of that vector, each on a row
Xu    % remove duplicate rows
!     % transpose
ttYs  % duplicate twice. Cumulative sum along each column
*     % element-wise product. Produces, in each column, indices for
      % elements of the first string; 1, 2,...,m. The rest are 0
w~    % swap, negate
tYs   % duplicate. Cumulative sum along each column
1Gn+  % add length of first input
*     % element-wise product. Produces, in each column, indices for
      % elements of the second string: m+1,...,m+n. The rest are 0
+     % add. This gives indices into the concatenated string created initially
!     % transpose back
)     % index into concatenated string. Implicitly display
Luis Mendo
sumber
0

Ruby, 83 byte

Fungsi rekursif yang kembali [a+b]jika salah satu dari string itu kosong. Jika tidak, ia mengembalikan daftar string yang a[0] + every string in v[a[1..-1],b]ditambahkan ke daftar stringb[0] + every string in v[a,b[1..-1]]

v=->a,b{a[0]&&b[0]?v[a[1..-1],b].map{|i|a[0]+i}+v[a,b[1..-1]].map{|i|b[0]+i}:[a+b]}
Sherlock9
sumber
0

Batch, 154 152 byte

@if "%~1%~2"=="" echo %3
@set t=%~1
@if not "%t%"=="" call %0 "%t:~1%" "%~2" %3%t:~,1%
@set t=%~2
@if not "%t%"=="" call %0 "%~1" "%t:~1%" %3%t:~,1%
Neil
sumber