Überprüfen Sie, ob die in Array aufgelisteten Zahlen dem Eingabeparameter

Question

entsprechen.

Ich befolge das Ruby-Übungsproblem von einer Website und bin völlig auf der Suche nach einer Lösung für dieses Problem. Bei einer Funktion has_sum?(val, arr) geben Sie true zurück, wenn eine beliebige Kombination von Zahlen im Array (zweiter Parameter) addiert werden kann, um dem ersten Parameter zu entsprechen, andernfalls wird false zurückgegeben. Also:

has_sum?(5, [1, 2, 3, 4]) # true

has_sum?(5, [1, 2, 6]) # false

bin ich ganz fest und nicht ganz sicher, wie dies zu tun ... Hier ist, was ich bisher haben.

def has_sum?(val, arr) 
    arr.each_with_index do |idx, v| 
    # ??? no idea what to do here except add the current num to the next in the list 
    end 
end 

Jede Hilfe würde sehr geschätzt werden - danke!

Answer 1

Ein Array kann eine Summe erzeugen, wenn eine Teilmenge von beliebiger Länge ist, das zu dieser Summe addiert:

def has_sum?(val, arr) 
    (arr.size + 1).times 
    .flat_map { |i| arr.combination(i).to_a } 
    .any? { |s| s.inject(:+) == val } 
end 

has_sum?(5, [5]) 
# => true 
has_sum?(5, [1, 2, 3]) 
# => true 
has_sum?(5, [1, 1, 1, 1, 1, 1]) 
# => true 
has_sum?(5, [1, 2, 7]) 
# => false 

Dies ist nicht sehr effizient, da es alle Möglichkeiten vor dem Test erzeugt. Dies sollte früher beenden:

def has_sum?(val, arr) 
    (arr.size + 1).times.any? { |i| 
    arr.combination(i).any? { |s| s.inject(:+) == val } 
    } 
end 

noch effizienter, eine rekursive Implementierung, mit der Idee, dass eine Summe eines leeren Array Null (und has_sum(nonzero, []) sollte return false); Für ein größeres Array wird der Kopf weggeklappt und geprüft, ob die Summe des Rests des Arrays in Ordnung ist, wenn wir das Kopfelement zählen oder nicht zählen. Hier führen wir nicht die nutzlose Summierung des gesamten Arrays immer wieder durch:

def has_sum?(val, arr) 
    if arr.empty? 
    val.zero? 
    else 
    first, *rest = arr 
    has_sum?(val, rest) || has_sum?(val - first, rest) 
    end 
end 

Answer 2

Ich würde verschachtelte Schleifen tun.

for x = 0 to length of array 
    for y = x + 1 to length of array 
     if number at x + number at y = sum return true 

return false 

Grundsätzlich wird es die Summe jeder Zahl mit jeder der Zahlen danach überprüfen.

EDIT: Dies wird nur 2 Zahlen gleichzeitig summieren. Wenn Sie in der Lage sein möchten, eine beliebige Anzahl von Zahlen zusammenzufassen, wird dies nicht funktionieren.

Answer 3

Diese Lösung verwendet dynamische Programmierung. Ich nehme an, dass Nullen aus dem Array entfernt wurden. Wenn alle Zahlen im Array positiv sind, können wir auch Elemente entfernen, die größer als die Zielsumme sind.

-Code

def sum_to_target(arr, target) 
    h = arr.each_index.with_object({}) do |i,h| 
    v = arr[i] 
    h.keys.each do |n| 
     unless h.key?(n+v) # || (n+v > target) 
     h[n+v] = v 
     return reconstruct(h, target) if n+v == target 
     end 
    end 
    h[v] = v unless h.key?(v) 
    return reconstruct(h, target) if v == target 
    end 
    nil 
end 

def reconstruct(h, target) 
    a = [] 
    loop do 
    i = h[target] 
    a.unshift i 
    target -= i 
    return a if target == 0 
    end 
    a 
end 

Zusätzliche Effizienzsteigerungen sind möglich, wenn arr nur postive Werte enthält.

Beispiele

# 1

sum_to_target [2,4,7,2], 8 
    #=> [2, 4, 2] 

# 2

arr = [64, 18, 64, 6, 39, 51, 87, 62, 78, 62, 49, 86, 35, 57, 40, 15, 74, 10, 8, 7] 
a = sum_to_target(arr, 461) 
    #=> [64, 18, 39, 51, 87, 62, 78, 62] 

Lasst uns, dass der Check.

a.reduce(:+) 
    #=> 461 

# 3

a = sum_to_target([-64, 18, 64, -6, 39, 51, -87, 62, -78, 62, 49, 86, 35, 57, 
        40, 15, -74, 10, -8, -7], 190) 
    #=> [18, 64, -6, 39, 51, -87, 62, 49] 

a.reduce(:+) 
    #=> 190 

# 4

arr = 1_000.times.map { rand 1..5_000 } 
    #=> [3471, 1891, 4257, 2265, 832, 1060, 3961, 875, 614, 2308, 2240, 3286, 
    # ... 
    # 521, 1316, 1986, 4099, 1398, 3803, 4498, 4607, 2262, 3941, 4367] 

arr ist ein Array aus 1.000 Elementen, die jeweils eine Zufallszahl zwischen 1 und 5.000.

answer = arr.sample(500) 
    #=> [3469, 2957, 1542, 950, 4765, 3126, 3602, 755, 4132, 4281, 2374, 
    # ... 
    # 427, 4238, 4397, 2717, 912, 1690, 3626, 169, 3607, 4084, 3161] 

answer ist ein Array aus 500 Elementen aus arr, ohne Ersatz entnommen.

target = answer.reduce(:+) 
    #=> 1_226_020 

target ist die Summe der Elemente der answer. Wir werden nun arr nach einer Sammlung von Elementen suchen, die zu 1,226,020 (answer, was eine solche Sammlung ist) summieren.

require 'time' 
t = Time.now 
    #=> 2016-12-12 23:00:51 -0800 

a = sum_to_target(arr, target) 
    #=> [3471, 1891, 4257, 2265, 832, 1060, 3961, 875, 614, 2308, 2240, 3286, 
    # ... 
    # 3616, 4150, 3222, 3896, 631, 2806, 1932, 3244, 2430, 1443, 1452] 

Beachten Sie, dass a != answer (was nicht überraschend ist).

a.reduce(:+) 
    #=> 1226020 

(Time.now-t).to_i 
    #=> 60 seconds 

Zu diesem letzten Beispiel Methoden, die Array#combination verwenden würde, obwohl so viele wie

(1..arr.size).reduce(0) { |t,i| t + arr.combination(i).size }.to_f 
    #~> 1.07+301 

Kombinationen waten.

Erklärung

arr = [2,4,7,2] 
target = 8 

Angenommen Lassen wir den Hash zurück übergeben, um es vorübergehend reconstruct neu zu definieren.

def reconstruct(h, target) 
    h 
end 

Wir erhalten dann die folgende:

h = sum_to_target(arr, target) 
    #=> {2=>2, 6=>4, 4=>4, 9=>7, 13=>7, 11=>7, 7=>7, 8=>2} 

h ist wie folgt definiert.

eine Reihe von Nicht-Null-Integer arr und eine Anzahl n, gegeben, wenn n ein Schlüssel von h wird ein Array a enthält Elemente aus arr, in der gleichen Reihenfolge, so dass die Elemente der a Summe n existiert und das letzte Element von a entspricht h[n].

die zugegebenermaßen ein Bissen ist.

Wir verwenden nun die reconstruct (wie in dem „Code“ Abschnitt definiert) ein Array answer zu konstruieren, die Elemente aus arr enthalten (ohne Elemente zu wiederholen), die Summe an target.

reconstruct(h, target) #=> [2, 4, 2] 

Zunächst initialisiert reconstruct das Array answer, die sie aufbauen und zurück:

answer = [] 

h immer einen Schlüssel enthalten, um gleiches Ziel (8). Wie h[8] #=> 2 schließen wir, dass das letzte Element von answer2 entspricht, so führen wir

answer.unshift(2) #=> [2] 

Das Problem ist jetzt eine Reihe von Elementen aus arr diese Summe zu 8 - 2 #=> 6 zu finden. Als h[6] #=> 4 schließen wir, dass das Element in answer, die die 2 voran wir nur 4 hinzugefügt:

answer.unshift(4) #=> [4, 2] 

Wir haben jetzt 8-2-4 #=> 2 mehr brauchen target insgesamt. Als h[2] #=> 2 führen wir

answer.unshift(2) #=> [2, 4, 2] 

Seit 8-2-4-2 #=> 0 wir fertig sind und daher answer zurück.

Beachten Sie, dass die letzte 42 in arr und den ersten 2 voran geht die 4 in arr. Der Weg h ist so konstruiert, dass die Elemente answer immer auf diese Weise bestellt werden.

Jetzt überlegen, wie h aufgebaut ist. Zuerst

h = {} 

Als arr[0] #=> 2 schließen wir, dass nur das erste Element arr verwenden, alles, was wir schließen können, ist:

h[2] = 2 
h #=> {2=>2} 

h hat keinen Schlüssel gleich target (8), so dass wir fortsetzen. Betrachten Sie nun arr[1] #=> 4. Mit nur die ersten beiden Elemente arr können wir schließen folgendes:

h[2+4] = 4 
h #=> {2=>2, 6=>4} 

und da h hat keinen Schlüssel 4,

h[4] = 4 
h #=> {2=>2, 6=>4, 4=>4} 

h noch kein Schlüssel gleich target (8) hat, so dass wir Drücken Sie auf und untersuchen Sie arr[2] #=> 7.nur die ersten drei Elemente arr Mit Wir schließen daraus folgendes:

h[2+7] = 7 
h[6+7] = 7 
h[4+7] = 7 
h #=> {2=>2, 6=>4, 4=>4, 9=>7, 13=>7, 11=>7} 

und da h hat keine Schlüssel 7:

h[7] = 7 
h #=> {2=>2, 6=>4, 4=>4, 9=>7, 13=>7, 11=>7, 7=>7} 

Wir vier Elemente h hinzugefügt, aber da arr enthält nur positive Zahlen, Die mit den Tasten , 13 und 11 sind von keinem Interesse.

Da h noch keinen Schlüssel gleich target hat (8), untersuchen wir das nächste Element in arr: arr[3] #=> 2. Mit nur die ersten vier Elemente arr schließen wir folgendes:

h[4+2] = 2 
h[6+2] = 2 

Hier stoppen wir, da 6+2 == target #=> true.

h #=> {2=>2, 6=>2, 4=>4, 9=>7, 13=>7, 11=>7, 7=>7, 8=>2} 

Beachten Sie, dass wir nicht h[2+2] = 2 seit h hat berechnen bereits eine Schlüssel 4. Hätten arr zusätzliche Elemente enthalten, hätten wir die Konstruktion des Hash zu diesem Zeitpunkt noch beendet.

Hätten wir den Code verändert sich die Tatsache zunutze zu tragen, dass arr nur positive Werte enthält, würde die endgültige Hash gewesen sein:

h #=> {2=>2, 6=>2, 4=>4, 7=>7, 8=>2} 

Wenn dies immer noch nicht klar ist, könnte es hilfreich sein, die laufen Code für dieses Beispiel mit den enthaltenen puts Anweisungen (zB puts "i=#{i}, h=#{h}, v=#{v}" nach der Zeile v = arr[i] in sum_to_target, und so weiter).

^{1 Die Zeile unless h.key?(n+v) kann in unless h.key?(n+v) || (n+v > target) geändert werden, wenn bekannt ist, dass das Array keine negativen Elemente enthält. (Dadurch wurde die Lösungszeit für Beispiel 4 um 4 Sekunden reduziert.) Man könnte auch @all_positive = arr.all?(&:positive?) berechnen und dann diese Zeile von @all_positive abhängig machen.}