배열에서 지정된 값을 더하는 모든 값을 찾습니다.

Question

대상 번호와 값 배열이있는 경우 대상 값까지 합한 모든 숫자 조합을 어떻게 찾을 수 있습니까?

target_number = 42 
sample_values = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28] 

여기에 대한 답변은 다음과 같습니다 내가 검색이 유형에 대한 mathmatical 용어, 당신을 위해 그것을 할 가능성이 루비 라이브러리가 확신

14 + 28 = 42 
13 + 27 = 42 
12 + 26 = 42 
... 
1 + 13 + 28 = 42 
2 + 12 + 28 = 42 
... 

.

중첩 된 for 루프없이 어떻게 할 수 있습니까?

sample_values.each do | x | 
    sample_values.each do | i | 
    sample_values.each do | j | 
     if x + i + j == target_number 
     puts "#{x} + #{i} + #{j} is #{target_number}" 
     end 
    end 
    end 
end 

Answer 1

이것은 Subset Sum 문제입니다.

Ruby combination 방법도 확인하십시오.

할 수있는 빠른 방법이 될 것이다 : 각각의

a = [1,2,3,4,5] 
arr = [] 
numOfCombinations = 0 

for i in 0..(a.length) do 
    a.combination(i).each do |b| 
    c = b.reduce(:+) 
     if c == target_number 
     numOfCombinations += 1 
     end 
    end 
end 

note: this is slow with a large number array

Answer 2

target_number = 42 
sample_values = (1..28).to_a 

(1..sample_values.length). 
    map { |length| sample_values.combination(length).to_a. 
    select { |candidate| candidate.reduce(:+) == target_number } 
    }.flatten(1) 

sample_values의 길이를 1에서 숫자의 범위에서 코드 반복을 생성하는 모든 조합 길이를 계산 한 다음 target_number에 합한 조합 만 필터링 한 다음 결과에서 중첩 수준을 하나 제거합니다.

1에서 28까지의 숫자 집합에서이 작업을 수행하려면 길이가 시간이 걸립니다. 예를 변경하여 1에서 20까지의 숫자 만 사용하면 몇 초 안에 결과가 나타납니다.

=> [[3, 19, 20], [4, 18, 20], [5, 17, 20], [5, 18, 19], [6, 16, 20], [6, 17, 19], [7, 15, 20], [7, 16, 19], [7, 17, 18], [8, 14, 20], [8, 15, 19], [8, 16, 18], [9, 13, 20], [9, 14, 19], [9, 15, 18], [9, 16, 17], [10, 12, 20], [10, 13, 19], [10, 14, 18], [10, 15, 17], [11, 12, 19], [11, 13, 18], [11, 14, 17], [11, 15, 16], [12, 13, 17], [12, 14, 16], [13, 14, 15], [1, 2, 19, 20], [1, 3, 18, 20], [1, 4, 17, 20], [1, 4, 18, 19], [1, 5, 16, 20], [1, 5, 17, 19], [1, 6, 15, 20], [1, 6, 16, 19], [1, 6, 17, 18], [1, 7, 14, 20], [1, 7, 15, 19], ...