모든 가능한 하위 집합을 계산하는 알고리즘

-1

이것은 매우 간단한 문제 여야합니다. 그러나 적절한 알고리즘 교육이 없으며이를 해결하기 위해 노력하고 있습니다.모든 가능한 하위 집합을 계산하는 알고리즘

더 작은 수의 제한된 세트를 함께 추가하여 가능한 조합을 계산해야합니다.

우리가 LEGO와 놀고 있으며 12 유닛 길이의 벽돌을 가지고 있다고 가정하면 더 짧은 벽돌로 가능한 대체품을 나열해야합니다. 이 예에서는 사용 가능한 벽돌이 2, 4, 6 및 12 단위라고 말할 수 있습니다.

하위를 계산할 수있는 알고리즘을 작성하는 좋은 방법은 무엇입니까? 한 번에 사용할 수있는 벽돌의 수에 제한이 없으므로 1x12뿐만 아니라 6x2 일 수도 있습니다. 중요한 점은 의 모든을 나열해야한다는 것입니다.

그래서 입력은 대상 길이 (이 경우 12)와 사용 가능한 벽돌 (숫자 배열 (임의의 길이),이 경우 [2, 4, 6, 12])입니다.

내 접근 방식은 낮은 숫자로 시작하여 목표에 도달 할 때까지 추가 한 다음 그 다음으로 낮게하는 등의 작업이었습니다. 그러나 그런 식으로 여러 숫자의 조합을 놓치고 그 요소를 분석하려고하면 정말 엉망이됩니다.

이 질문에 대한 답은 투표가 잘못 되었습니까? – yizzlez

http://stackoverflow.com/questions/3420937/algorithm-to-find-which-number-in-a-list-sum-up-to-a-certain-number와 비슷할 수도 있습니다. – Bharat

@awesomeyi 나는 추측 할 수 있습니다. ,하지만 ... OP가 제공 한 접근법은 코드 또는 의사 코드없이 OP가 잘못 될 경우에만 추측 할 수 있습니다 ... 많은 목록이 있습니다. 모두 - 여기에 질문을 제출하십시오. – Dukeling

내가 재귀 접근 방식을 제안한다 permissibles의 조합으로 target의 모든 표현을 표시하는 기능 f(target,permissibles) 주어,이 작업을 수행 할 수 있습니다

def f(target,permissibles): 
    for x in permissibles: 
    collect f(target - x, permissibles)

당신이 12 = 4+4+2+2 및 12=2+4+2+4 구별하지 않으려면

, permissibles을 내림차순으로 정렬해야합니까?

2014-06-12 01:57:16 sds

제안 해 주셔서 감사합니다. 불행히도 나는 파이썬 녀석이 아니므로, 예제가 분명해 보일지라도 '수집하는'것에 대해서는 혼란 스럽다. 루비로 변환 할 수 있다면 슈퍼가 도움이 될 것입니다. 그러나 그렇지 않으면 수집하지 않는 부분이 있습니다. – funkylaundry

Ruby에 대해 잘 모릅니다. 내 코드는 파이썬이 아니다. 수집은 값을 누적 기 (accumulator)에 넣고 함수의 종료시 내용을 반환하는 것을 의미합니다. – sds

좋습니다. 고마워요. 루비에서 복제 할 수 있는지 확인합니다. 당신의 예제는 어떤 언어로 쓰여졌습니까? – funkylaundry

답변