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, a
selalu sebelumnya b
, dan c
selalu 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.
sumber
Jawaban:
Pyth, 26
Coba di sini
Ini adalah implementasi yang sangat mendasar dari formula rekursif yang diberikan. Ini mendefinisikan fungsi
g
yang 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 lakukang<string1><string2>
.Ekspansi:
Dua panggilan rekursif sangat mirip, tetapi saya belum dapat menemukan cara untuk golf mereka lagi.
sumber
Haskell,
5348 byteMenentukan fungsi
%
yanga%b
dengan stringa,b
memberikan 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:
Menentukan fungsi
%
yanga%d
dengan stringa,d
memberikan 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.
sumber
""%""=[""]
.Haskell, 47
%
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).sumber
(#) :: [a]->[a]->[[a]]
, jadia::[a]
dan hasilnya harus tipe[[a]]
Python 2, 71 byte
Contoh dijalankan:
Diberikan dua string,
x,y
kita dapat mengambil karakter pertamax
dan menambahkannya ke setiap hasil panggilan rekursif dengan hilangf(x[1:],y)
. Atau, kita dapat melakukan hal yang sama denganx
dany
beralih. Dengan mengambilx,y
inputp
atau pembalikannya `p [:: - 1], kita mendapatkan kedua kemungkinan.Untuk menghindari pengambilan dari string kosong
x
, kami melakukan hubungan arus pendek denganx and
. Jika kedua string kosong, string tidak dapatx
dan kami mendapatkan dan mengosongkan daftar kemungkinan, yang kami perbaiki denganor
kasus dasar yang benar['']
.Strategi generatif serupa di Python 3 (73 byte):
sumber
Python, 80
Seperti yang diminta, inilah jawaban python:
Terima kasih Sp3000 untuk makan 4 byte :)
sumber
CJam, 38
Cobalah online
Pemrograman dinamis (menggunakan rekursi memoized).
Penjelasan:
sumber
CJam, 32 byte
Uji di sini.
Ini terasa sangat golf, tetapi sejauh ini saya hanya menemukan 4 solusi alternatif yang semuanya memiliki jumlah byte yang sama:
Ide dasarnya adalah untuk menghasilkan semua permutasi dari
0
s dan1
s terkait dengan string mana untuk mengambil setiap karakter dalam hasil dari. Itu semuanya terserah dan termasuke!
. Sisanya hanya mengeluarkan karakter dalam urutan itu dari dua string itu.sumber
e*
dan.*
yang mengulangi setiap elemen dengan jumlah yang berbeda. ;) (Yaitu operator yang harus dilakukan:a.*:~
. Saya kirae*
dapat digunakan untuk itu karena saat ini kesalahan jika diberi dua daftar.)JavaScript (Firefox 30-57),
888481 byteSunting: Disimpan 4 byte dengan meningkatkan kondisi terminasi saya. Disimpan 3 byte berkat @ edc65.
sumber
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))
v
sebagai kondisinya, tetapi tidak pernah terpikir oleh saya untuk menggunakannyav[1]
.Brachylog , 8 byte
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.)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
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.)sumber
MATL ,
3430 byteIni menggunakan ide dari jawaban ini : jika panjang string adalah
m
dann
, sebutkan semuam+n
polam
bit dengan bit yang ditetapkan. Salah satu cara melakukan itu penghitungan adalah: menghasilkan semua permutasi dari vektor denganm
satu dann
nol dan kemudian menghapus duplikat.Cobalah online!
Penjelasan
sumber
Ruby, 83 byte
Fungsi rekursif yang kembali
[a+b]
jika salah satu dari string itu kosong. Jika tidak, ia mengembalikan daftar string yanga[0] + every string in v[a[1..-1],b]
ditambahkan ke daftar stringb[0] + every string in v[a,b[1..-1]]
sumber
Batch,
154152 bytesumber