0

私はPythonでバックトラックを介してアレンジメントを生成する方法を理解しようとするのに苦労しています、それは彼らが大学で私たちに尋ねたものです

1からnまでの番号が付けられたn人（n <= 10）のグループが椅子の列に配置されますが、2人の隣人ごとにいくつかの利害の対立が現れました。対立している2人の間で、1人または多くても2人の他の人がとどまるように、人を置き換えるために可能なすべてのモダリティを表示します。

順列と女王のコードを変更することができましたが、条件をどこに置くかは本当にわかりません。たとえば、kは数字であり、kは文字列+1の前の数字とは異なる必要があり、次の番号+1

椅子に座っている人のリストは123 4です（3人未満では不可能です）1つの正しい解決策は1 342と3142になります

コードは次のとおりです。

class Permutations(Backtracking):

    def __init__(self, n):
        Backtracking.__init__(self, n)

    def _init_value(self, k):
        return 0

    def _next_value(self, n, k, v):
        if v < n:
            return v + 1
        return None

    def _cond(self, k, possible, v):
        if v is None:
            return False
        try:
            possible[:k].index(v) 
            return False
        except ValueError:
            return True

    def _solution(self, n, k, possible):
        return k == n-1

    def _handle_solution(self, n, k, possible):
        print(possible)
4

2 に答える 2

2 
def chairs(soln, i=0):
    if i == len(soln):
        yield tuple(soln)
    for j in xrange(i, len(soln)):
        if i == 0 or soln[j] not in (soln[i - 1] + 1, soln[i - 1] - 1):
            soln[i], soln[j] = soln[j], soln[i]
            for s in chairs(soln, i + 1):
                yield s
            soln[i], soln[j] = soln[j], soln[i]

print list(chairs(range(1, 5)))
于 2013-01-02T16:47:46.680 に答える
1

コード：

def possible_solution(remaining, sol=None):
    sol = sol or []
    if not remaining:
        yield sol
    else:
        for i, candidate in enumerate(remaining):
            if not sol or abs(sol[-1] - candidate) != 1:
                new_sol = sol + [candidate]
                new_remaining = remaining[:i] + remaining[i+1:]
                for x in possible_solution(new_remaining, new_sol):
                    yield x

テストコード:

def possible_solutions(neighbors):
    for solution in possible_solution(neighbors):
        print solution

print '-' * 30
possible_solutions([1, 2, 3])

print '-' * 30
possible_solutions([1, 2, 3, 4])

print '-' * 30
possible_solutions([1, 2, 3, 4, 5])

結果：

------------------------------
------------------------------
[2, 4, 1, 3]
[3, 1, 4, 2]
------------------------------
[1, 3, 5, 2, 4]
[1, 4, 2, 5, 3]
[2, 4, 1, 3, 5]
[2, 4, 1, 5, 3]
[2, 5, 3, 1, 4]
[3, 1, 4, 2, 5]
[3, 1, 5, 2, 4]
[3, 5, 1, 4, 2]
[3, 5, 2, 4, 1]
[4, 1, 3, 5, 2]
[4, 2, 5, 1, 3]
[4, 2, 5, 3, 1]
[5, 2, 4, 1, 3]
[5, 3, 1, 4, 2]
于 2013-01-02T17:03:41.403 に答える