Temukan Faktor Subset

14

Mari kita bayangkan kita memiliki satu set bilangan bulat positif yang terbatas. Set ini dapat direpresentasikan sebagai garis titik di mana setiap bilangan bulat yang ada di set diisi seperti scantron atau kartu punch . Misalnya set {1,3,4,6}dapat direpresentasikan sebagai:

*.**.*

*mewakili anggota himpunan kami dan .mewakili bilangan bulat yang bukan merupakan anggota yang ia tetapkan.

Set ini memiliki "faktor". Longgar x adalah faktor y jika y dapat dibangun dari salinan x. Lebih tepatnya definisi faktor kita adalah sebagai berikut:

  • x adalah faktor y jika dan hanya jika y adalah gabungan dari sejumlah set yang terpisah , yang semuanya x dengan offset.

Kami akan memanggil *.*sebuah faktor dari *.**.*karena cukup jelas terdiri dari dua salinan *.*put ujung ke ujung.

*.**.*
------
*.*...
...*.*

Faktor tidak harus ujung ke ujung, kami juga akan mengatakan itu *.*adalah faktor*.*.*.*

*.*.*.*
-------
*.*....
....*.*

Faktor-faktor juga bisa tumpang tindih. Ini berarti *.*juga merupakan faktor****

****
----
*.*.
.*.*

Namun angka tidak dapat ditutupi oleh faktor lebih dari sekali. Sebagai contoh *.*adalah bukan faktor *.*.*.

Berikut ini contoh yang lebih rumit:

 *..*.**..***.*.*

Ini *..*.*sebagai faktor. Anda dapat melihat di bawah di mana saya telah berbaris tiga contoh *..*.*.

*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*

Tugas

Diberikan satu set oleh keluaran representasi yang masuk akal semua set yang merupakan faktor input.

Anda dapat mengindeks dengan nilai apa pun, (yaitu Anda dapat memilih angka terkecil yang dapat hadir dalam input). Anda juga dapat mengasumsikan bahwa set input akan selalu mengandung nilai sekecil itu.

Ini adalah pertanyaan kode-golf sehingga Anda harus berusaha melakukan ini dalam sesedikit mungkin byte.

Uji Kasus

Kasus uji ini dilakukan dengan tangan, mungkin ada satu atau dua kesalahan pada kasus yang lebih besar

*                -> *
*.*.*            -> *, *.*.*
*.*.*.*          -> *, *.*, *...*, *.*.*.*
******           -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.**  -> *, *...**.**, *.....*, *...*****.**.**
code-golf combinatorics set-partitions set-theory Posting Rock Garf Hunter
sumber
Jika kita menganggap himpunan sebagai daftar angka (mis. [1,3,5,7]Untuk *.*.*.*) dapatkah kita menganggapnya diurutkan?
Martin Ender
1
Apakah ini setara dengan mencari pembagi polinomial yang koefisiennya dibatasi hingga 0 dan 1?
xnor
1
@ xnor saya tidak yakin. Jika *.*.*= x+x^2+x^4, maka 1+x+x^2= ***akan menjadi pembagi, kan? x+x^2+x^4 = (1-x+x^2)(1+x+x^2)
mbomb007
1
@JonathanAllan Sebagai contoh, *tercantum sebagai faktor yang mewakili subset yang sama dengan *.atau *...
Martin Ender
1
@ JonathanAllan Dikatakan output semua set, bukan output semua representasi ASCII dari set yang valid.
Martin Ender

Jawaban:

3

Mathematica, 71 68 byte

#&@@@Cases[(s=Subsets)@s@#,x_/;Sort[Join@@x]==#&&Equal@@(#&@@@x-x)]&

Input sebagai {1,3,5,7}(diurutkan) dan output sebagai {{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. Fungsi ini akan membuang banyak pesan.

Ini adalah O (2 2 Tidak ) (di mana N adalah panjang input dan o = p = e = 1 ...). Ini menghasilkan semua himpunan bagian dari himpunan bagian, kemudian memilih orang-orang yang menghasilkan pengiriman input ketika bergabung bersama (memastikan kami hanya mempertimbangkan partisi) dan di mana semua elemen adalah sama jika kita mengurangi nilai terkecil dari setiap subset).

Martin Ender
sumber
2

Jelly , 12 byte

;÷@DỊȦ
ÆDçÐf

Input dan output digunakan 1dan 0bukannya *dan ..

Cobalah online!

Bagaimana itu bekerja

ÆDçÐf   Main link. Argument: n (integer with decimal digits 1 and 0)

ÆD      Compute all divisors of n.
  çÐf   Filter; call the helper link with left argument d and right argument n for
        all divisors d of n. Return the array of d's for which the helper link
        returns a truthy value.


;÷@DỊȦ  Helper link. Left argument: d. Right argument: n

 ÷@     Divide n by d.
;       Concatenate, yielding [d, n÷d].
   D    Decimal; convert both integers in the pair to base 10.
    Ị   Insignificant; map 1 and 0 to 1, all other positive integers to 0.
     Ȧ  All; return 1 iff the result contains no zeroes.
Dennis
sumber