Jumlah output unik dengan mengganti variabel

9

Diberikan serangkaian formula seperti ini:

bacb
bcab
cbba
abbc

Berikan algoritme yang menemukan jumlah hasil unik yang bisa Anda dapatkan ketika setiap variabel diganti dengan "0" atau "1" di setiap rumus.

Ada (k!)^2rumus, masing-masing dengan 2k-1variabel dan k^2istilah. Ekspresikan asimptotik Anda dalam hal k.

Algoritma tercepat menang. Dalam kasus seri, solusi dengan penggunaan memori asimptotik yang lebih rendah akan menang. Jika itu masih seri, pos pertama menang.

Untuk contoh di atas, hasil berikut dapat diperoleh dengan mengganti variabel:

1110, 0110, 1001, 0100, 1000, 0000, 0010, 1101, 1111, 0001, 1011, 0111

Jadi jawaban yang benar adalah 12. Antara lain, 1010tidak bisa dibuat menggunakan rumus di atas.

Saya telah membuat tiga lagi test case, dengan masing-masing solusi 230 , 12076 dan 1446672 .

combinatorics fastest-algorithm orlp
sumber
Klarifikasi: apa yang k dalam pertanyaan? Apakah ini hanya konstanta abstrak?
isaacg
@isaacg Ya. Ini untuk mencegah ikatan antara solusi yang lebih cepat untuk formula yang lebih sedikit tetapi lebih besar, misalnya.
orlp
Jadi setiap huruf a, b, ... adalah variabel ? Dan kita selalu memiliki jumlah variabel yang tidak merata? Tidak masalah berapa lama urutan variabelnya, dan berapa banyak formula yang diberikan?
flawr
@ flawr Hubungan yang tepat antara jumlah variabel, jumlah istilah dan jumlah rumus diberikan dalam pertanyaan.
orlp
Apakah 'bisa' berarti Anda bisa mendapatkan hingga $ (k!) ^ 2 $ rumus atau apakah ada tepat $ (k!) ^ 2 $ rumus? Selain itu, apakah Anda memiliki aplikasi untuk algoritma dengan spesifikasi tersebut? Saya hanya bertanya karena spesifikasi tampaknya cukup arbitrer.
flawr

Jawaban:

2

Mathematica, O (k ^ 2 (k!) ^ 2) waktu

Length[Union@@(Fold[Flatten[{StringReplace[#,#2->"0"],StringReplace[#,#2->"1"]}]&,#,Union[Characters[#]]]&/@#)]&

Semoga saya menghitung kompleksitas waktu dengan benar. Input adalah daftar formula seperti {"bacb","bcab","cbba","abbc"}. Berjalan kurang dari 30 detik untuk setiap test case di komputer saya, tetapi siapa yang peduli dengan waktu absolut?

Penjelasan:

  • Pertama, &pada akhirnya menjadikannya fungsi murni, dengan #merujuk pada argumen pertama, #2menjadi argumen kedua, dll.
  • Length[*..*] membutuhkan panjang daftar yang ada di dalamnya.
  • Union@@(*..*)mengambil daftar yang ada dan menyediakannya sebagai argumen untuk Union, yang mengembalikan daftar elemen unik di salah satu argumennya.
  • *..*&/@#mengambil fungsi murni dan memetakannya di atas daftar rumus, sehingga {a,b,c}menjadi {f[a],f[b],f[c]}. Perhatikan bahwa dalam fungsi murni bersarang, #nmerujuk ke argumen paling dalam.
  • Fold[*..*&,#,*..*]mengambil fungsi akumulator, nilai awal, dan daftar, dan kembali f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] mengambil semua karakter dalam rumus saat ini dan mendapatkan semua elemen unik, memberi kita variabel.
  • Flatten[*..*]meratakan argumennya, sehingga {{{a},b},{{c,{d}}}}menjadi {a,b,c,d}.
  • {*..*,*..*}hanyalah cara untuk menggabungkan dua hasil menggunakan di atas Flatten.
  • StringReplace[#,#2->"0/1"]mengambil hasil sebelumnya dan mengembalikannya dengan variabel saat ini diganti dengan salah satu 0atau 1.
LegionMammal978
sumber
Mengapa Anda menggunakan ksebagai variabel dalam waktu Anda? Tetap saja, waktu faktorial! Fiuh!
theonlygusti
Op mengatakan: "Ekspresikan asimptotik Anda dari segi k." Juga, saya harus melakukan GeneralUtilities`Benchmarkuntuk setiap metode yang digunakan.
LegionMammal978
Ingin menambahkan deskripsi bahasa Inggris sederhana untuk algoritme Anda? Saya tidak terbiasa dengan Mathematica, jadi saya tidak dapat memverifikasi solusi Anda.
orlp