Set aditif unik N

10

Ingatlah bahwa satu set tidak diurutkan tanpa duplikat.

Definisi Sebuah N -uniquely aditif set S yang panjangnya K adalah satu set sedemikian rupa sehingga semua N -Panjang subset di S sum ke nomor yang berbeda. Dengan kata lain, jumlah dari semua himpunan bagian panjang N dari S semuanya berbeda.

Objective Diberikan array / set sebagai input dan angka Nke fungsi atau ke program lengkap dalam format yang masuk akal, menemukan dan mengembalikan atau menampilkan nilai yang benar atau salah (kesalahan untuk falsey tidak apa-apa) yang menunjukkan apakah input tersebut N - aditif unik.

Anda dapat mengasumsikan bahwa setiap elemen hanya muncul paling banyak satu kali dan bahwa setiap angka berada dalam tipe data asli bahasa Anda. Jika perlu, Anda juga dapat mengasumsikan bahwa input diurutkan. Terakhir, Anda dapat menganggap itu 0 < N <= K.

Contohnya

Mari kita pertimbangkan set S = {1, 2, 3, 5}dan N = 2. Berikut ini semua jumlah semua pasangan unik S(untuk yang unik adalah satu-satunya yang menarik untuk jumlah):

1 + 2 = 3
1 + 3 = 4
1 + 5 = 6
2 + 3 = 5
2 + 5 = 7
3 + 5 = 8

Kita dapat melihat bahwa tidak ada duplikat dalam output, jadi S adalah aditif 2-unik.


Sekarang mari kita pertimbangkan set T = {12, 17, 44, 80, 82, 90}dan N = 4. Berikut ini semua jumlah panjang yang mungkin dari empat:

12 + 17 + 44 + 80 = 153
12 + 17 + 44 + 82 = 155
12 + 17 + 44 + 90 = 163
12 + 17 + 80 + 82 = 191
12 + 17 + 80 + 90 = 199
12 + 17 + 82 + 90 = 201
12 + 44 + 80 + 82 = 218
12 + 44 + 80 + 90 = 226
12 + 44 + 82 + 90 = 228
12 + 80 + 82 + 90 = 264
17 + 44 + 80 + 82 = 223
17 + 44 + 80 + 90 = 231
17 + 44 + 82 + 90 = 233
17 + 80 + 82 + 90 = 269
44 + 80 + 82 + 90 = 296

Mereka semua unik, dan T adalah aditif 4-unik.

Uji Kasus

[members], N => output
[1, 4, 8], 1 => true
[1, 10, 42], 1 => true                ; all sets trivially satisfy N = 1
[1, 2, 3, 4], 3 => true
[1, 2, 3, 4, 5], 5 => true
[1, 2, 3, 5, 8], 3 => true
[1, 2, 3, 4, 5], 2 => false           ;  1 +  4       =  5 =        2 + 3
[-2, -1, 0, 1, 2], 3 => false         ; -2 + -1 + 2   = -1 =   -2 + 0 + 1
[1, 2, 3, 5, 8, 13], 3 => false       ;  1 +  2 + 13  = 16 =    3 + 5 + 8
[1, 2, 4, 8, 16, 32], 3 => true
[1, 2, 4, 8, 16, 32], 4 => true
[1, 2, 4, 8, 16, 32], 5 => true
[1, 2, 4, 8, 16, 32], 6 => true
[3, 4, 7, 9, 12, 16, 18], 6 => true
[3, 4, 7, 9, 12, 16, 18], 3 => false  ; 3 + 4 + 12 = 19 = 3 + 7 + 9
Conor O'Brien
sumber
Maksudmu N <= K?
Neil
@Neil Ya, saya lakukan. Maaf!
Conor O'Brien
Apakah kesalahan dihitung sebagai sesuatu falsey?
flawr
@ flawr Tentu, saya akan menerimanya
Conor O'Brien

Jawaban:

3

MATL , 7 byte

XN!sSdA

Cobalah online!

Mengembalikan true(ditampilkan sebagai 1) atau false(ditampilkan sebagai 0).

XN   % Take array S and number N. Generate all combinations of elements from S 
     % taken N at a time. Gives a 2D array where each combination is a row
!    % Transpose. Each combination is now a column
s    % Sum of each column: gives a row array. If N=1 computes the sum of
     % the only row, and so gives a number
S    % Sort vector
d    % Array of consecutive differences. For a single number gives an empty array
A    % True if all elements of the input array are nonzero (for an empty array
     % it also gives true)
Luis Mendo
sumber
4

Jelly, 7 byte

œcS€ṢIP

Cobalah online!

Mengembalikan angka positif untuk kebenaran dan nol untuk falsey.

œc       find combinations
  S€     sum each combination
    Ṣ    sort the sums
     I   find the difference between each pair of sums 
           iff any sums are the same, this returns a list containing 0
      P  product of the elements of the resulting list
Gagang pintu
sumber
3

Matlab, 78 byte

function n=f(s,n);p=perms(s);k=sum(unique(sort(p(:,1:n)),'rows')');unique(k)-k

Fungsi ini mengembalikan nilai positif (pada kenyataannya n) untuk kebenaran dan mengembalikan kesalahan sebagai jawaban palsu (valid menurut komentar ini )

Penjelasan:

function n=f(s,n);
p=perms(s); %create all permutations of the set

k=sum(unique(sort(p(:,1:n)),'rows')');
                  %just take the first n entries of each permutation
             %sort those entries and
      %filter out all duplicates (we sorted as the order should NOT matter)
  %then sum each of those candidates

unique(k)-k
%if all those sums are distinct, unique(k) will have the same size 
% as k itself, and therefore we can subtract, otherwise it will throw 
% an error as we try to subtract vectors of different sizes
cacat
sumber
Mengapa itu salah?
Conor O'Brien
1
Saya baru saja menambahkan penjelasan. Kesalahan berasal dari baris terakhir. Ini menyebabkan kesalahan jika kami memiliki duplikat di k. PS: Penyorotan sintaksis Matlab akhirnya bekerja !!!
flawr
Ide bagus untuk kembali sama n!
Luis Mendo
2

Pyth, 8 byte

{IsM.cFQ

Suite uji.

       Q   eval input (provided as a 2-element array)
    .cF    splat over combination
  sM       sum each combination
{I         is the result invariant under { (dedup/uniq)?
Gagang pintu
sumber
Apa splatartinya
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Hal yang sama artinya dalam setiap bahasa lain: gunakan array sebagai argumen untuk suatu fungsi.
Gagang Pintu
Oh, benar, aku bodoh: terima kasih
Conor O'Brien
2
dalam setiap bahasa lain yang sebenarnya memiliki fungsi ini
flawr
2
Saya memperbaiki bug yang mengharuskannya Qpada akhirnya.
isaacg
2

Haskell, 69 byte

import Data.List
n#s=(==)=<<nub$[sum x|x<-subsequences s,length x==n]

Contoh penggunaan: 6 # [3,4,7,9,12,16,18]-> True.

Implementasi langsung dari definisi: buat daftar jumlah semua urutan panjang n dan periksa apakah sama dengan duplikat yang dihapus.

nimi
sumber
2

JavaScript (ES6), 132 byte

(a,n)=>a.map(m=>{for(i=n;i--;)s[i].map(k=>s[i+1].push(m+k))},s=[...Array(n+1)].map(_=>[]),s[0]=[0])&&new Set(s[n]).size==s[n].length

Buat daftar aditif dari 1 hingga n dan kemudian periksa yang terakhir untuk keunikan.

Neil
sumber
2

Brachylog , 20 byte

:1f:+aLdL
[L:I]hs.lI

Mengharapkan daftar yang berisi daftar dan kemudian bilangan bulat sebagai Input, dan tidak ada Output, misalnya run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2])..

Penjelasan

  • Predikat Utama

               Input = [A:I]
    :1f        Find all ordered subsets of A of length I
       :+aL    Apply summing to each element of that list of subsets. Call that L
           dL  True if L minus all duplicate elements is still L
    
  • Predikat 1: Temukan semua himpunan bagian yang dipesan dengan panjang yang tetap dari suatu daftar

    [L:I]      Input = [L:I]
         hs.   Unify Output with an ordered subset of L
            lI True if I is the length of Output
    
Fatalisasi
sumber
2

Julia, 46 41 byte

x\n=(t=map(sum,combinations(x,n)))==tt

Cobalah online!

Bagaimana itu bekerja

Ini (kembali) mendefinisikan operator biner \untuk argumen Array / Int.

combinations(x,n)mengembalikan semua array dengan tepat n elemen x yang berbeda . Kami memetakan di sumatas array ini dan menyimpan hasilnya di t .

t∪tmelakukan penyatuan set array t dengan dirinya sendiri, yang bekerja seperti lebih lama uniquedalam kasus ini.

Akhirnya, kami membandingkan t dengan deduplicated t , mengembalikan truejika dan hanya jika semua jumlah berbeda.

Dennis
sumber
2

Python, 89 byte

from itertools import*
lambda s,n,c=combinations:all(x^y for x,y in c(map(sum,c(s,n)),2))

Uji di Ideone .

Bagaimana itu bekerja

c(s,n)daftar semua n -kombinasi s , yaitu, semua daftar n elemen s . Kami memetakan sumdaftar yang dihasilkan, sehingga menghitung semua jumlah yang mungkin dari daftar panjang n .

Setelah bangsal, kami gunakan c(...,2)untuk membuat semua pasangan jumlah yang dihasilkan. Jika ada dua jumlah x dan y yang sama, x^yakan mengembalikan 0 dan allakan mengembalikan False . Sebaliknya, jika semua jumlah adalah unik, x^yakan selalu benar, dan anyakan mengembalikan Benar .

Dennis
sumber
1

J, 34 byte

load'stats'
[:*/@~:[:+/"1(comb#){]

Pendekatan straight-forward, hanya membutuhkan statsadd-on untuk combfungsi tersebut. Pengembalian 0untuk false dan 1true.

Sebagai alternatif untuk menggunakan combbuiltin, ada solusi 38 byte yang menghasilkan set daya dan memilih subset ukuran n .

[:*/@~:(>@{[:(</.~+/"1)2#:@i.@^#)+/@#]

Pemakaian

   f =: [:*/@~:[:+/"1(comb#){]
   2 f 1 2 3 5
1
   4 f 12 17 44 80 82 90
1
   3 f _2 _1 0 1 2
0
   6 f 3 4 7 9 12 16 18
1
   3 f 3 4 7 9 12 16 18
0
mil
sumber
Wow, tidak tahu tentang statsmodul. Sangat bagus!
Conor O'Brien
Saya baru tahu tentang itu juga, saya belum benar-benar mempelajari banyak add-on di J. Jika saya lebih berani, saya akan mencoba add-on grafis.
mil
0

Ruby , 50 byte

->s,n{!s.combination(n).map{|c|c.inject :+}.uniq!}

Cobalah online!

Jika semua elemen unik, uniq!kembali nil. Meniadakan hasil itu, seperti dalam !(...).uniq!membuat untuk tes keunikan yang bagus.

Pertanyaan ini diposting beberapa minggu sebelum Ruby 2.4.0-preview1, yang diperkenalkan Enumerable#sum, yang akan menghemat 9 byte di sini.

41 byte (Ruby 2.4+)

->s,n{!s.combination(n).map(&:sum).uniq!}

Cobalah online!

benj2240
sumber
0

R , 41 byte

function(s,n)max(table(combn(s,n,sum)))<2

Jumlah semua himpunan bagian panjang s dan periksa apakah semua nilai dalam tabel kontingensi dari jumlah ini adalah 1 (semua jumlah adalah unik).

Cobalah online!

Robert Hacken
sumber