1

我正在做一些算法问题，并在我的一个测试用例中遇到了一个奇怪的问题。该get_num_groups函数返回一个由断言语句验证的整数。

list(set(words))在我在函数中引入该行之后，第一个断言语句似乎间歇性地通过。

代码：

def are_similar(w1, w2):
    '''
        returns true if swapping the positions of exactly 2 characters
        in a word makes the given words equal
    '''
    if len(w1) != len(w2):
        return False

    mis_matches = 0
    locs = []
    n = len(w1)

    for i in range(n):
        if w1[i] != w2[i]:
            mis_matches += 1
            locs.append(i)

    if mis_matches != 2:
        return False

    # check if the 2 letter swap will result in equal words
    return w1[locs[0]] == w2[locs[1]] and w1[locs[1]] == w2[locs[0]]


def get_group(graph, n, word_i):
    # for a word at the word_i'th position, get all words connected to it

    group = set()
    stack = [word_i]

    while stack:
        i = stack.pop()

        # view all nodes connected directly/indirectly to i'th node
        for neigh in range(i, n):
            if graph[i][neigh] != 0:
                group.add(neigh)
                stack.append(neigh)
                graph[neigh][i] = 0
                graph[i][neigh] = 0

    return group


def get_num_groups(words):
    '''
        - creates a graph of words that are connected if similar.
        - does a dfs/bfs traversal to collect count of the disconnected sub graphs
    '''
    words = list(set(words)) # causes a strange intermittent bug. in first testcase
    n = len(words)
    # n X n adj matrix
    graph = [[0] * n for _ in range(n)]

    # create graph
    for i in range(n):
        graph[i][i] = 1 # word is connected to itself
        wi = words[i]
        for j in range(i+1, n):
            wj = words[j]
            s = are_similar(wi, wj)
            if s:
                graph[i][j] = 1
                graph[j][i] = 1

    num_groups = 0
    for i in range(n):
        g = get_group(graph, n, i)
        if g:
            num_groups += 1

    return num_groups


if __name__ == '__main__':
    # === Test ===
    wds = ["tars", "rats", "star", "arts"]
    num_ways = get_num_groups(wds)

    inp = (wds)
    res = (num_ways)
    expected = (2)
    assert res == expected, '[Fail] {} -> {}\nexpected:{}'.format(inp, res, expected)
    print('[+]')

    # === Test ===
    wds = []
    num_ways = get_num_groups(wds)

    inp = (wds)
    res = (num_ways)
    expected = (0)
    assert res == expected, '[Fail] {} -> {}\nexpected:{}'.format(inp, res, expected)
    print('[+]')

    # === Test ===
    wds = ["ss", "ss"]
    num_ways = get_num_groups(wds)

    inp = (wds)
    res = (num_ways)
    expected = (1)
    assert res == expected, '[Fail] {} -> {}\nexpected:{}'.format(inp, res, expected)
    print('[+]')

    # === Test ===
    wds = ["ssa", "ssb"]
    num_ways = get_num_groups(wds)

    inp = (wds)
    res = (num_ways)
    expected = (2)
    assert res == expected, '[Fail] {} -> {}\nexpected:{}'.format(inp, res, expected)
    print('[+]')

使用命令运行时出现意外输出while true; do python3 file.py; done：

+]
[+]
[+]
[+]
Traceback (most recent call last):
  File "p.py", line 110, in <module>
    assert res == expected, '[Fail] {} -> {}\nexpected:{}'.format(inp, res, expected)
AssertionError: [Fail] ['tars', 'rats', 'star', 'arts'] -> 3
expected:2
Traceback (most recent call last):
  File "p.py", line 110, in <module>
    assert res == expected, '[Fail] {} -> {}\nexpected:{}'.format(inp, res, expected)
AssertionError: [Fail] ['tars', 'rats', 'star', 'arts'] -> 3
expected:2
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]
[+]

这是极不可能的，但是，这样list(set(<some array>))做的方式是否存在python中的错误？

4

0 回答 0