Herausforderung

Angenommen, Sie haben eine Liste mit Zahlen und einen Zielwert. Suchen Sie die Menge aller Kombinationen Ihrer Zahlen, die sich zum Zielwert addieren, und geben Sie sie als Listenindizes zurück.

Ein- und Ausgang

Die Eingabe wird eine Liste von Zahlen (nicht unbedingt eindeutig) und eine Zielsummierungsnummer nehmen. Die Ausgabe besteht aus einer Reihe nicht leerer Listen, wobei jede Liste ganzzahlige Werte enthält, die der Position der Werte in der ursprünglichen Eingabeliste entsprechen.

Beispiele

Input: values = [1, 2, 1, 5], target = 8
Output: [ [0,1,3], [1,2,3] ]

Input: values = [4.8, 9.5, 2.7, 11.12, 10], target = 14.8
Output: [ [0,4] ]

Input: values = [7, 8, 9, -10, 20, 27], target = 17
Output: [ [1,2], [0,3,4], [3,5] ]

Input: values = [1, 2, 3], target = 7
Output: [ ]

Wertung

Das ist Code-Golf , also gewinnt der kürzeste Code!

Schale , 10 Bytes

ηλfo=¹ṁ⁰tṖ

1-indiziert. Probieren Sie es online!

Erläuterung

ηλfo=¹ṁ⁰tṖ  Inputs are a number n (explicit, accessed with ¹) and a list x (implicit).
η           Act on the incides of x
 λ          using this function:
         Ṗ   Take all subsets,
        t    remove the first one (the empty subset),
  f          and keep those that satisfy this:
      ṁ⁰      The sum of the corresponding elements of x
   o=¹        equals n.

Dies verwendet die neueste Ergänzung zu Husk η(auf Indizes einwirken). Die Idee ist, dass man ηeine Funktion höherer Ordnung α(hier die Inline - Lambda - Funktion) und eine Liste xnimmt und αdie Indexierungsfunktion von x(die ⁰im obigen Programm enthalten ist) und die Indizes von aufruft x. Nimmt beispielsweise ṁ⁰eine Teilmenge von Indizes, ordnet die Indizierung xdiesen zu und summiert die Ergebnisse.

JavaScript (ES6), 96 Byte

Übernimmt Eingaben in der Currying-Syntax (list)(target).

a=>s=>a.reduce((b,_,x)=>[...b,...b.map(y=>[...y,x])],[[]]).filter(b=>!b.reduce((p,i)=>p-a[i],s))

Testfälle

Dies würde im 2. Testfall fehlschlagen, wenn 4.8 und 10 aufgrund eines IEEE 754-Präzisionsfehlers vertauscht würden - dh 14.8 - 4.8 - 10 == 0aber 14.8 - 10 - 4.8 != 0. Ich denke, das ist in Ordnung , obwohl es irgendwo in Meta eine relevantere Referenz geben kann.

let f =

a=>s=>a.reduce((b,_,x)=>[...b,...b.map(y=>[...y,x])],[[]]).filter(b=>!b.reduce((p,i)=>p-a[i],s))

console.log(JSON.stringify(f([1, 2, 1, 5])(8)))
console.log(JSON.stringify(f([4.8, 9.5, 2.7, 11.12, 10])(14.8)))
console.log(JSON.stringify(f([7, 8, 9, -10, 20, 27])(17)))
console.log(JSON.stringify(f([1, 2, 3])(7)))

Kommentiert

a => s =>                 // given an array a[] of length N and an integer s
  a.reduce((b, _, x) =>   // step #1: build the powerset of [0, 1, ..., N-1]
    [ ...b,               //   by repeatedly adding to the previous list b[]
      ...b                //   new arrays made of:
      .map(y =>           //     all previous entries stored in y[]
        [...y, x]         //     followed by the new index x
      )                   //   leading to:
    ],                    //   [[]] -> [[],[0]] -> [[],[0],[1],[0,1]] -> ...
    [[]]                  //   we start with a list containing an empty array
  )                       // end of reduce()
  .filter(b =>            // step #2: filter the powerset
    !b.reduce((p, i) =>   //   keeping only entries b
      p - a[i],           //     for which sum(a[i] for i in b)
      s                   //     is equal to s
    )                     //   end of reduce()
  )                       // end of filter()

Python 2 , 110 Bytes

lambda a,n:[b for b in[[i for i in range(len(a))if j&1<<i]for j in range(2**len(a))]if sum(a[c]for c in b)==n]

Probieren Sie es online!

R , 85 84 Bytes

function(l,k){N=combn
o={}
for(i in I<-1:sum(l|1))o=c(o,N(I,i,,F)[N(l,i,sum)==k])
o}

Probieren Sie es online!

1-indiziert.

combnGibt normalerweise a zurück matrix, aber die Einstellung simplify=Fgibt liststattdessen a zurück, sodass wir calle Ergebnisse zusammen verketten können. combn(I,i,,F)gibt alle Indexkombinationen zurück und wir nehmen sie N(l,i,sum)==kals Index in diese Liste, um diejenigen zu bestimmen, die gleich sind k.

J , 32 31 Bytes

(=1#.t#])<@I.@#t=.1-[:i.&.#.1"0

Probieren Sie es online!

                  1-[:i.&.#.1"0         Make a list of all masks
                                        for the input list. We flip the bits
                                        to turn the unnecessary (0...0)         
                                        into (1...1) that would be missing.
                                        Define it as t.

(=1#.t#])                               Apply the masks, sum and
                                        compare with the target

         <@I.@#                         Turn the matching masks into 
                                        lists of indices

Japt , 14 Bytes

m, à f_x!gU ¥V

Online testen!

Wie es funktioniert

m, à f_x!gU ¥V   Implicit: U = input array, V = target sum
m,               Turn U into a range [0, 1, ..., U.length - 1].
   à             Generate all combinations of this range.
     f_          Filter to only the combinations where
       x           the sum of
        !gU        the items at these indices in U
            ¥V     equals the target sum.
                 Implicit: output result of last expression

Sauber , 104 102 98 Bytes

import StdEnv
@n=[[]:[[i:b]\\i<-[0..n-1],b<- @i]]
?l n=[e\\e<-tl(@(length l))|sum(map((!!)l)e)==n]

Probieren Sie es online!

Haskell , 76 Bytes

x#t=[i|i<-tail$concat<$>mapM(\z->[[],[z]])[0..length x-1],t==sum[x!!k|k<-i]]

Probieren Sie es online!

Jelly , 11 Bytes

ị³S=
JŒPçÐf

Probieren Sie es online!

1-indiziert. 4 Bytes für die Rückgabe von Indizes und nicht nur für die Elemente selbst.

-1 Byte danke an user202729
-1 Byte danke an Jonathan Allan

Wolfram-Sprache (Mathematica) , 43 Byte

1-indiziert.

Pick[s=Subsets;s@Range@Tr[1^#],Tr/@s@#,#2]&

Probieren Sie es online!

Python 3 , 144 Bytes

lambda a,t:[[e for e,_ in x]for r in range(len(a))for x in combinations(list(enumerate(a)),r+1)if sum(y for _,y in x)==t]
from itertools import*

Probieren Sie es online!

0-indiziert. 44 Byte werden für die Rückgabe von Indizes und nicht nur für die Elemente selbst ausgegeben.

Brachylog , 18 15 Bytes

hiᶠ⊇Shᵐ+~t?∧Stᵐ

Probieren Sie es online!

-3 Bytes, weil es jetzt als Generator arbeitet . (Es ist wahrscheinlich möglich, mehr Golf zu spielen, aber die Notwendigkeit, Indizes zu verwenden, ist umständlich.)

    S              The variable S
   ⊇               is a sublist of
  ᶠ                the list of all
 i                 pairs [element, index] from
h                  the first element of
                   the input;
     hᵐ            the first elements of each pair
       +           add up to
        ~t         the last element of
          ?        the input
           ∧       which isn't necessarily
            S      S,
             tᵐ    from which the last elements of each pair
                   are output.

Perl 6 , 45 Bytes

->\a,\b{grep {a[$_].sum==b},^a .combinations}

Probier es aus

Erweitert:

->
  \a, # input list
  \b, # input target
{

  grep

  {
      a[ $_ ].sum # use the list under test as indexes into ｢a｣
    ==
      b
  },

  ^a              # Range upto ｢a｣ (uses ｢a｣ as a number)
  .combinations   # get all of the combinations
}

APL (NARS), 49 Zeichen, 98 Byte

{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}

1-indiziert; Prüfung:

  f←{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}
  ⎕fmt 8 f 1 2 1 5
┌2──────────────┐
│┌3────┐ ┌3────┐│
││2 3 4│ │1 2 4││
│└~────┘ └~────┘2
└∊──────────────┘
  ⎕fmt   14.8  f  4.8 9.5 2.7 11.12 10
┌1────┐
│┌2──┐│
││1 5││
│└~──┘2
└∊────┘
  ⎕fmt 17 f 7, 8, 9, ¯10, 20, 27
┌3──────────────────┐
│┌2──┐ ┌2──┐ ┌3────┐│
││4 6│ │2 3│ │1 4 5││
│└~──┘ └~──┘ └~────┘2
└∊──────────────────┘
  ⎕fmt 7 f 1 2 3
┌0┐
│0│
└~┘

Kommentar:

{∨/b←⍺=+/¨{∊⍵⊂w}¨n←{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵:⍸¨b/n⋄⍬}
                             ⍳¯1+2*k←≢w←⍵         copy ⍵ in w, len(⍵) in k, return 1..2^(k-1) 
                 n←{⍵⊤⍨k⍴2}¨                     traslate in binary each element of  1..2^(k-1) and assign the result to n
          {∊⍵⊂w}¨                                for each binary element of n return the elemets of ⍵ in the place where there are the 1s
    b←⍺=+/¨                                       sum them and see if the sum is ⍺, that binary array saved in b
  ∨/                                     :⍸¨b/n   if or/b, get all the elements of n that are 1s for array b, and calculate each all indexs
                                               ⋄⍬ else return Zilde as void set

Pyth, 11 Bytes

fqvzs@LQTyU

Versuchen Sie es online hier oder überprüfen alle Testfälle auf einmal hier .

fqvzs@LQTyUQ   Implicit: Q=input 1 (list of numbers), z=input 2 (target value, as string)
               Trailing Q inferred
          UQ   Generate range [0-<length of Q>)
         y     Powerset of the above
f              Keep elements of the above, as T, when the following is truthy:
      L T        Map elements of T...
     @ Q         ... to the indicies in Q
    s            Take the sum
 q               Is the above equal to...
  vz             z as an integer
               Implicit print of the remaining results