python - ワンループ？パイソン

Question

そこで、可能な数が与えられたこの関数を書きました。与えられた数を構成する可能な数の中から 2 つの数を見つけなければなりません。しかし、私はまだ Python (非常に素晴らしい言語) を学んでいるので、限られた機能セットしか使用できません。

この関数を作成しました：

def sumPair(theList, n):

    theList = charCount(theList) #charCount is a function i made to convert the list into a dictionary
    for i in theList:
        for a,b in theList.iteritems():
            print a,b
            if a + i == n:
                if theList[b] > 1:
                    return [i, b]
                if a != i:
                    return [i, b]
        return "[]"
print sumPair([6,3,6,8,3,2,8,3,2], 11)   

私が言ったように、それは与えられた数になる 2 つの数を見つけます。charCount配列を辞書に追加する私が書いた関数です。

このプログラムでは、加算される数値が同じ場合に備えて、値が 1 より大きいことを確認します。場合によっては、10 の合計をチェックして 5 を指定すると、その 5 を自分自身に加算して 10 を返すことがあります。これが がある理由if theList[b] > 1: です。

なぜ私はここにいるのですか？私のインストラクターは 2 つのループに満足していませんでした。トラブルシューティングに5時間費やしましたが、どこにも行きませんでした。このプログラムを単一のループ プログラムに変換する必要があります。

私はこれに一日中費やしました。あなたに宿題をさせようとしているわけではありません。私は本当に行き詰まっており、あなたの助けが必要です。これを行うためのキーが存在するかどうかを確認する必要があると聞いたことがあります。

Answer 1

インストラクターは、アルゴリズムに必要以上に時間がかかることに不満を持っているでしょう。これを試して：

for each element x in theList
  if there exists an element y in theList such that x+y = n, you have a match

「存在する場合」テストを高速にする必要があります。これは、辞書を使用するためのものです。1 回のループでこの辞書が構築され、2 回目のループで検索が行われます。これには、O(n^2) 時間に対して直線的な時間がかかります。

あなたのポイント 5 自体とのマッチングは良いものです。マルチセットまたはバッグと呼ばれるデータ構造を使用したい。それについて読んでから、次のようにコードを実装してください。

for each element x in theList
  if there exists an element y in theList such that x+y == n:
    if x != y or (x == y and x occurs more than once):
      you have a match

幸運を。

EDIT非常に多くの準最適なソリューションがあるため、ここに単純な線形ソリューションがあります（リストには2つのループがあるため線形ですが、ループは次々に発生します。したがって、2 * n反復、O（n）。は非常に高速です。

#!/usr/bin/python2.6

from collections import defaultdict

def sum_list(l, n):
  count = defaultdict(lambda: 0)

  for x in l:      # O(n)
    count[x] += 1  # This can be done in constant time O(1)

  for x in l:      # O(n)
    y = n - x
    if count[y] > 0 and (x != y or count[y] > 1): # O(1)
      return x, y

Answer 2

特殊なケースを個別に確認できます。n%2「n mod 2」を意味するので、偶数の0場合ですn

def sumPair(theList, n):
    # If n is even, check whether n/2 occurs twice or more in theList
    if n%2 == 0 and theList.count(n/2) > 1:
        return [n/2, n/2]

    theSet = set(theList)
    for i in theSet:
        if n-i in theSet:
            return [i, n-i]
    return []

Answer 3

純粋な python - ライブラリは使用されていません:

def combinations(lst):
    l = lst[:] # copy of source list
    while len(l) > 1:
        a = l.pop(0)
        for b in l:
           yield a,b

def first_pair(iterator):
    for i in iterator:
       # just return first element
       return i

def sum_pair(lst, sum_val):
    return first_pair((a,b) for a,b in combinations(lst) if (a+b) == sum_val)

print sum_pair([6,3,6,8,3,2,8,3,2], 11)
# result (3,8)

itertools を使用:

from itertools import combinations, islice

def sum_pair(lst, sum_val):
    return list(islice(((a,b)
        for a,b in combinations(lst, 2) if (a+b) == sum_val), 0, 1))

print sum_pair([6,3,6,8,3,2,8,3,2], 11)
# result [(3,8)]

Answer 4

これは非常に良い質問です。一定の空間で線形時間でそれを行う方法を尋ねられたことがありますが、今日まで、これを達成する方法がわかりません。

これは単純な実装です。キャッシュを使用して少し高速化する方法があると確信していますが、リスト内のすべての整数が一意ではないことを前提としています。

def get_sum_pairs(sum = None, list_of_numbers = None):
    assert sum != None and list_of_numbers != None
    list_of_numbers = sorted(list_of_numbers) # sort the list of numbers O(n log n)        
    for index, number in enumerate(list_of_numbers): # search for each number that is less than the sum O(n)
        if number < sum: # if number greater then sum, theres nothing we can do.
            for index, number_1 in enumerate(list_of_numbers[(index + 1):]): # search the second list, this isn't exactly O(n) since its incremented being incremented
                if number + number_1 == sum: # found a solution.
                    return [(number, number_1)]
                if (number_1 > sum) or (number + number_1 > sum): # if number greater then sum, theres nothing we can do.
                    break                                       # if the addition of two sorted numbers is greater then sum, then theres no need to keep searching since the rest will also be greater, since their sorted.
        else:
            break
    return [()]

唯一の方法は、残念ながら私が持っていない数式またはトリックを使用することです。

実行時間を測定する場合、ほとんどの場合、最悪のシナリオを考慮します。この場合、各数値が合計よりも小さく、一意である数値のリストになります。

そのため、n 個の一意の数値はすべて合計より少なくなります。並べ替えを行うと、1 + 2 == 2 + 1 であるため、前に進むだけで済むため、チェックの数を減らすことができます :) が、2 + 3、3 + をチェックする必要があります。 4など...しかし、チェックされた合計がそれよりも大きい場合、合計が増加するため、合計を与えることも停止できることに注意してください... :)

ここにいくつかのテストがあります...

assert all([get_sum_pairs(**test[0]) == test[1] for test in
     [({'list_of_numbers':[6,3,6,8,3,2,8,3,2], 'sum':11}, [(3, 8)]),
     ({'list_of_numbers':[1,2,3,4,1,2], 'sum':1}, [()]),
     ({'list_of_numbers':[1,2,3,1,23,1,23,123], 'sum':124}, [(1, 123)]),
     ({'list_of_numbers':[1,2,3,12,3,2,1,23,4,1,23,4,5,12332], 'sum':14}, [(2, 12)]),
     ({'list_of_numbers':[-1,2,-2, -3, 1, 2, 3, 2, -1.3], 'sum':1}, [(-1, 2)])
     ] ])

Answer 5

@samy.vilarの「一定空間」についてはわかりませんが、線形の時間と空間であるソリューションを次に示します（nではなく に比例しますlen(numbers)）：

def sumpairs(numbers, n):
    numbers = [None] + numbers + [None] * (n-len(numbers))
    for k in range(len(numbers)):
        a = numbers[k]
        if a is None or a==k: continue
        if numbers[n-a]==n-a:
            return a, n-a
        numbers[k] = None
        while numbers[a] != a and a is not None:
            b = n-a
            if numbers[a] is None:
                numbers[a] = a
                break
            if numbers[b]==b:
                return a, n-a
            numbers[a], a = a, numbers[a]

print(sumpairs([6,3,6,8,3,2,8,3,2], 16))
print(sumpairs([6,3,6,8,3,2,8,3,2], 11))
print(sumpairs([6,3,5,8,3,2,8,3,2], 10))
print(sumpairs([6,3,5,8,3,2,8,3,2], 5))
print(sumpairs([6,3,5,8,3,2,8,3,2], 12)) # This should fail.

各数値をリスト内の対応する位置に移動することで機能します ( None1 ベースのインデックスを取得するために先頭を追加しました)。複雑さは少しトリッキーです: 入れ子になったループがありますが、各数値がその位置を変更されるのは、プロセス全体がまだ O(n) であるためです。

n数値リストの長さと比較して が大きい場合、その解決策はもちろんひどいものです。これは、一定のスペース（入力を破棄する場合、それ以外の場合はその単一のコピーが必要です）であり、入力の長さである n に対して O(n log n) 時間であるソリューションです。

def sumpairs(numbers, n):
    numbers = sorted(numbers)
    low = 0
    while low < len(numbers)-1:
        t = numbers[low] + numbers[-1]
        if t > n:
            numbers.pop(-1)
        elif t < n:
            low += 1
        else:
            return numbers[low], numbers[-1]

print(sumpairs([6,3,6,8,3,2,8,3,2], 16))
print(sumpairs([6,3,6,8,3,2,8,3,2], 11))
print(sumpairs([6,3,5,8,3,2,8,3,2], 10))
print(sumpairs([6,3,5,8,3,2,8,3,2], 5))
print(sumpairs([6,3,5,8,3,2,8,3,2], 12)) # This should fail.

Answer 6

私のコメント:

• リストを辞書に変換する場合は、名前を からtheList別の名前に変更します。theList辞書を保持するという変数があると混乱します。

• 2 つの数値が常に隣り合って検出される場合は、インデックス変数iを 0 に設定して をインクリメントし、目的の数値と等しいiかどうかを確認するループを作成してみてください。theList[i] + theList[i + 1]

• 2 つの数字が隣り合って見つからない可能性がある場合は、さらに注意が必要です。最も明白な方法は、2 つのループを使用することです。1 つは各数値を順番に調べ、もう 1 つは次の数値を調べて、それらの合計が目標になるかどうかを確認します。2 つの数値が隣り合っている必要がなく、インストラクターがループを 1 つだけ使用することを希望している場合は、リストの値を保持するために何か (辞書など) を使用するか、「暗黙のループ"。

「暗黙のループ」とはどういう意味ですか? inPython には、オブジェクトが Python リストにあるかどうかを示す演算子 が用意されています。これはリストをループすることで機能しますが、ループを記述しません。ループは Python の内部で行われます。

したがって、次のように行うことができます。各数値を順番に見てください。ターゲット値から数値を減算しin、計算された値がリストの残りの部分にあるかどうかを確認するために使用します。リストの残りを検索し、現在の値をスキップするには、「リスト スライス」を使用します。スライシングをまだ学んでいない場合、インストラクターはおそらくリスト スライシングの答えを探していません。

ここに例があります。0にi設定し、リストの最初のエントリを見ている場合、値は 6 です。ターゲット値は 11 です。したがって、計算された値は (11 - 6) または 5 です。computed_value in theList. リストの残りの部分だけを見るには、スライスを使用できますcomputed_value in theList[1:]。インデックス変数がある場合、次のiようなものがcomputed_value = 11 - theList[i]あり、かどうかを確認しますcomputed_value in theList[i:]。

• forループを使用して 0 からリストの長さまでのインデックスを作成し、そのインデックスを使用してリストにインデックスを作成できることを忘れないでください。Python では通常、リストから連続するオブジェクトにfor x in lst:which セットを使用するのが最善ですが、使用してからorまたはor を使用すると便利な場合に問題が発生することがあります。xfor i in xrange(len(lst)):lst[i]lst[i+1]lst[i:]

• 教師が希望するコーディング スタイルを使用してください。先生が「theList」のような「camelCase」の名前が必要な場合は、そうしてください。しかし、Python の通常のスタイルは "PEP 8" と呼ばれ、そのスタイルの変数名は "the_list" のようにアンダースコア付きの小文字です。 http://www.python.org/dev/peps/pep-0008/