0

これで、すでに午後の半分を占めていました...ネストされたリストの最後と最初の要素を連鎖させようとしています。これを簡単な例で説明します。

input = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14), 
         (14, 3), (7, 4), (3, 4)]
result = [(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7),
          (7, 6), (6, 5), (5, 8)]

次のコードを試しました：

def ChainNew(L):
    R = copy.deepcopy(L)
    for pair in R:
        pair.reverse()
    stop = len(L)
    chain = [L.pop(0)]
    L = sorted(L)
    R = sorted(R)
    while len(chain) < stop:
        for i, j in zip(L, R):
            if i[0] == chain[len(chain)-1][1]:
                chain.append((i))
                L.remove(i)
                R.remove(i[::-1])
                break
            if j[0] == chain[len(chain)-1][1]:
                chain.append((j))
                L.remove(j[::-1])
                R.remove(j)
                break
    return chain

しかし、これは非効率的であるだけでなく、バ​​グもあります: 初期リストのすべての要素を返すようには見えません。例えば：

L =  [[20, 56], [23, 24], [23, 12], [22, 21], [26, 48], [26, 24],
      [55, 48], [55, 39], [56, 40], [19, 6], [19, 12], [6, 15],
      [40, 39], [21, 57], [14, 15], [14, 16], [57, 50], [45, 9],
      [45, 53], [18, 42], [18, 9], [38, 53], [38, 44], [50, 42],
      [16, 17], [17, 35], [36, 37], [36, 35], [37, 44]]

return = [[20, 56], [56, 40], [40, 39], [39, 55], [55, 48], [48, 26],
          [26, 24], [24, 23], [23, 12], [12, 19], [19, 6], [6, 15], 
          [15, 14], [14, 16], [16, 17], [17, 35], [35, 36], [36, 37], 
          [37, 44], [44, 38], [38, 53], [53, 45], [45, 9], [9, 18], 
          [18, 42], [42, 50], [50, 57]]

これを行う簡単な方法があるはずです...

編集：ごめんなさい！各リスト (ペア) 内の整数を交換できることを忘れていました。たとえば、(7, 4) から (4, 7) です。

基本的に、ここで数値の各ペアに含まれているのは、ポリラインのエッジのインデックスです。すべてのエッジが一緒になってポリラインを形成します。したがって、数値の各ペアを「連鎖」させることで、ポリラインの頂点のインデックスをソートされた方法で取得できます。

もう一度編集: リスト L の正しい結果は次のようになります。

return = [[22, 21], [21, 57], [57, 50], [50, 42], [42, 18], [18, 9],
          [9, 45], [45, 53], [53, 38], [38, 44], [44, 37], [37, 36],
          [36, 35], [35, 17], [17, 16], [16, 14], [14, 15], [15, 6],
          [6, 19], [19, 12], [12, 23], [23, 24], [24, 26], [26, 48],
          [48, 55], [55, 39], [39, 40], [40, 56], [56, 20]]

ありがとう！

4

2 に答える 2

2

どうですか：

def path(a, b):
    if not b:
        return a
    for n, (p, q) in enumerate(b):
        if p == a[-1][1]:
            return path(a + [(p, q)], b[:n] + b[n+1:])
        if q == a[-1][1]:
            return path(a + [(q, p)], b[:n] + b[n+1:])
    raise ValueError("no path", a, b)

L = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14), (14, 3), (7, 4), (3, 4)]
print path([L[0]], L[1:])
#[(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7), (7, 6), (6, 5), (5, 8)]
于 2013-10-05T17:29:26.393 に答える
1

考えられるすべてのチェーンを見つけるソリューションは次のとおりです。

def find_chains(points):
    """For a list of points, take the first point and finds all chains that
    could be made from the following points.

    Returns a list of lists of tuples. Each sublist is a possible chain.
    """

    def find_solutions(start, choices):
        """For a starting point and a list of choices, return all choices that
        might succeed that point.

        Returns a list of tuples. These tuples contain the next choice, and all
        of the remaining points should that choice be used.
        """

        ret = []
        for i, possible_choice in enumerate(choices):
            # Determine whether or not the choice is appropriate.
            added_choice = None
            if start[1] == possible_choice[0]:
                added_choice = possible_choice
            elif start[1] == possible_choice[-1]:
                added_choice = possible_choice[::-1]

            # If it is, add a tuple of that choice and all other choices to the
            # return list.
            if added_choice:
                ret.append((
                    added_choice,
                    [
                        k
                        for j, k
                        in enumerate(choices)
                        if i != j
                    ]
                ))

        return ret

    solutions = []
    start = points[0]
    other_points = points[1:]
    if not other_points:
        # If there aren't any remaining points, then the only possible path is
        # that of just the first point.
        return [[start]]

    # Find all chains through `other_points` and add them to our solutions.
    for next_point, remaining_points in find_solutions(start, other_points):
        for subchain in find_chains([next_point] + remaining_points):
            solutions.append([start] + subchain)
    return solutions

この解決策と他のより短い解決策との違いは、他の解決策は最初の可能な点を取り、そこからサブチェーンを見つけるだけであるのに対し、この解決策は可能なすべての点を取ることです。例：

test = [(1, 2), (2, 3), (2, 4), (3, 4)]
print(find_chains(test))
# Finds two possible solutions:
# [[(1, 2), (2, 3), (3, 4), (4, 2)],
#  [(1, 2), (2, 4), (4, 3), (3, 2)]]

test = [(8, 2), (8, 5), (2, 12), (12, 13), (5, 6), (6, 7), (13, 14),
        (14, 3), (7, 4), (3, 4)]
print(find_chains(test))
# Finds the only solution:
# [[(8, 2), (2, 12), (12, 13), (13, 14), (14, 3), (3, 4), (4, 7), (7, 6), (6, 5), (5, 8)]]

test = [(1, 2), (3, 4)]
print(find_chains(test))
# There weren't any solutions:
# []
于 2013-10-05T17:54:10.067 に答える