더 구체적으로하려면 정수 n과 행렬이 주어진 경우 모든 조합을 반환하는 알고리즘 (재귀 적 또는 비 반복적)이 필요합니다. 각 라인 2)에서 1) 적어도 1 개체를해야합니까 N 내가 그냥 모든 조합을 시도하는 경우이 쉽게 해결 n은 객체와 1에서이 사람을 사용할 수 있습니다 느낄다른 빈에서 가져온 n 개의 객체의 가능한 모든 조합을 반환하는 알고리즘
총 객체 : 그 것 각 라인,하지만 그 알고리즘이 훨씬 더 효율적일 수 있다고 생각합니다. 한 줄에 1 개체의 모든 조합을 반환하지만 더 이상 확장 할 수없는 알고리즘도 성공적으로 코딩했습니다. 필자는 파이썬으로 코딩을 해왔지만, 어떤 언어에서도 괜찮습니다. 파이썬이 참조 당 객체를 전달한다는 것에 대한 추가 포인트. =)
행렬을 제곱한다고 가정합니다. 왜 누군가가 이유를 알고 싶다면, 이것은 제가 풀려고하는보다 복잡한 그래프 알고리즘의 일부입니다.
감사합니다.
감사합니다 모든 해답을 위해, 그들은 내가 찾던에 가까웠다. 내가 파이썬에서 관리했기 때문에 (여기에 게시 된 결과를 확인하지 않았다.) 실제로 문제는 Python이 함수 호출에서 참조 대 사본을 전달하는 것이었다. 나는 얕은 사본이 충분했을 것이라고 생각했지만 분명히 나는 깊은 사본을 필요로했다. (왜 얕은 것이 충분하지 않은지를 생각하지 않았다.)
이것은 내가 한 방법입니다.
PS1 : 그래프는 목록의 사전입니다. n_edges는 그래프에서 선택한 모서리 수입니다.
PS2 : 크기 계산은 매우 비효율적이며 아직 수정하지 않았습니다.
PS3 : 사전에 질서 정연하게 반복하기 위해 그래프 목록 (lol)과 그에 일치하는 색인 배열 (lolindex)의 두 목록을 만들었습니다.
PS4 : 게시 한 질문에 맞도록 수정되었으므로 실제 사용한 방법에는 문제가있는 특정 코드가 있습니다. 코드를 여기에 입력하는 방식으로 테스트하지 않았습니다.
def pickEdges(n_edges, newgraph):
size = sum(len(v) for v in newgraph.itervalues())
if (size == n_edges):
print newgraph
return
for i in range(len(lol)):
for j in range(len(lol[i])):
tmpgraph = copy.deepcopy(newgraph)
if (lol[i][j] not in tmpgraph[lolindex[i]]):
tmpgraph[lolindex[i]].append(lol[i][j])
pickEdges(n_edges, tmpgraph)
행렬 m이 목록 목록이라고 가정합니다. 여기에 라켓 기능이 있습니다 :
(define (combinations m n)
(cond
((and (zero? n) (null? m)) '(()))
((zero? n) '())
((null? m) '())
((null? (car m)) '())
(else
(append (combinations (cons (cdar m) (cdr m)) n)
(map (lambda (ls) (cons (caar m) ls))
(append
(combinations (cons (cdar m) (cdr m)) (sub1 n))
(combinations (cdr m) (sub1 n))))))))
대부분의 경우 작업을 수정하고 간단한 목록의 모든 조합을 나열 하시겠습니까? 아래는 당신을 위해이 작업을 수행하는 자바 스크립트 함수이다 :
function getWayStr(curr) {
var nextAbove = -1;
for (var i = curr + 1; i < waypoints.length; ++i) {
if (nextAbove == -1) {
nextAbove = i;
} else {
wayStr.push(waypoints[i]);
wayStr.push(waypoints[curr]);
}
}
if (nextAbove != -1) {
wayStr.push(waypoints[nextAbove]);
getWayStr(nextAbove);
wayStr.push(waypoints[curr]);
}
}
어떤 좋은 질문이 있습니까? 용어와 일치하도록 행렬의 행을 "입력 bags"으로, 입력 백의 항목을 "객체"라고합니다. bag (또는 multiset)은 멤버가 두 번 이상 표시되지만 멤버에는 목록과 달리 고유 한 순서가없는 컨테이너를 허용합니다.
우리는 다음과 같은 서명 기능을 찾고 있습니다 :
set of valid combinations =
generate_combinations(list of input bags, number of objects in valid combination)
이 유효 조합의 세트 파이썬에서 사용할 수있는 메모리를 초과 할 수 있기 때문에
이generate_combinations 명시 적 목록보다는 발전기를 반환해야합니다.
: I는 다음과 같은데이 각 입력 백
개체 :
유효한 결과는 다음 조건을 만족해야
요구 # 않고 물체를 끌어 (두 입력 잡화 같을 수도 축퇴 경우) 중복 객체를 포함 할 수있는 중복 된 객체를 포함 할 1 명 가정 # 4 의미 number of input bags <= n <= total number of objects in all bags
데이터 구조
파이썬의 내장 된 itertools 모듈을 사용하여 v2.6에서 소개 된 조합을 생성합니다. 이전 버전의 Python을 사용하고 있다면 레시피를 사용하십시오. 이 코드 예제에서는 명확하게하기 위해 생성기를 목록으로 암시 적으로 변환했습니다.
>>> import itertools, collections
>>> input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
>>> output_bag_size = 5
>>> combos = generate_combinations(input_bags, output_bag_size)
>>> combos.next() #an arbitrary example
Bag([1,1,2,4,12])
>>> all_objects = itertools.chain.from_iterable(input_bags)
>>> all_objects
generator that returns [1, 2, 2, 3, 5, 1, 4, 5, 9, 12]
>>> combos = itertools.combinations(all_objects, output_bag_size)
>>> combos
generator that returns [(1,2,2,3,5), (1,2,2,3,1), (1,2,2,3,4), ...]
겹치기를 처리하려면 [가방의 추가 요소]에서 [각 입력 봉투의 요소 1 개]에서 요소를 제거하고 for 루프를 제거합니다.
>>> combos_with_one_element_from_each_bag = itertools.product(*input_bags)
>>> for base_combo in combos_with_one_element_from_each_bag:
>>> all_objects = list(itertools.chain.from_iterable(input_bags))
>>> for seen in base_combo:
>>> all_objects.remove(seen)
>>> all_objects_minus_base_combo = all_objects
>>> for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
>>> yield itertools.chain(base_combo, remaining_combo)
제거 작업은 목록에서 지원되지만 발전기에서는 지원되지 않습니다.all_objects를 메모리에리스트로 저장하지 않으려면 base_combo의 요소를 건너 뛰는 함수를 작성하십시오.
>>> def remove_elements(iterable, elements_to_remove):
>>> elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
>>> for item in iterable:
>>> if item not in elements_to_remove_copy:
>>> yield item
>>> else:
>>> elements_to_remove_copy.remove(item)
가방 클래스의 구현은 다음과 같습니다
>>> class Bag(collections.Counter):
>>> def __iter__(self):
>>> return self.elements()
>>> def remove(self, item):
>>> self[item] -= 1
>>> if self[item] <= 0:
>>> del self[item]
전체 코드
import itertools, collections
class Bag(collections.Counter):
def __iter__(self):
return self.elements()
def remove(self, item):
self[item] -= 1
if self[item] <= 0:
del self[item]
def __repr__(self):
return 'Bag(%s)' % sorted(self.elements())
def remove_elements(iterable, elements_to_remove):
elements_to_remove_copy = Bag(elements_to_remove) #create a soft copy
for item in iterable:
if item not in elements_to_remove_copy:
yield item
else:
elements_to_remove_copy.remove(item)
def generate_combinations(input_bags, output_bag_size):
combos_with_one_element_from_each_bag = itertools.product(*input_bags)
for base_combo in combos_with_one_element_from_each_bag:
all_objects_minus_base_combo = remove_elements(itertools.chain.from_iterable(input_bags), base_combo)
for remaining_combo in itertools.combinations(all_objects_minus_base_combo, output_bag_size-len(base_combo)):
yield Bag(itertools.chain(base_combo, remaining_combo))
input_bags = [Bag([1,2,2,3,5]), Bag([1,4,5,9]), Bag([12])]
output_bag_size = 5
combos = generate_combinations(input_bags, output_bag_size)
list(combos)
마침 같은 output_bag_size로 (오류 검사 코드를 추가하여이 해제 > = len (input_bags)
이 접근 방식의 적합성은 다음과 같습니다. 1. 유지 보수가 덜 필요한 코드 (즉, itertools) 2. 재귀가 발생하지 않습니다. 파이썬 성능은 호출 스택 높이에 따라 저하되므로 재귀를 최소화하는 것이 좋습니다. 3. 최소 메모리 사용. 이 알고리즘은 입력 백 목록에 의해 소비되는 것 이상의 일정 공간 메모리를 필요로합니다.