1

私はそのような数字のリストを持っています（ランダムに生成され、各サブグループ内でソートされた数字。グループは互いに素であるため、複数のグループで特定の数字を見つけることはできません）：

L=[[19,18,14,9,4],[15,12,11,10,6,5],[8],[16,13,3,2],[17,7,1]]

減少するトリプレットを作成できる方法の数を数えようとしています。

減少トリプレットは、リストを左から右にスキャンし、グループから要素 1 を取り出し、次に別のグループから要素 2 を取り出し、次に別のグループから要素 3 を取り出すトリプレットであり、最終結果は自然に降順になります。

たとえば、(19,11,7) は有効な減少するトリプレットです。これは、これらの数値が異なるサブリストから取得され、減少する自然な順序になっているためです (19 は 11 の前にあり、マスター リストでは 7 の前に来ます)。

反例で明確にするために: (15, 9, 8) は、9 が 15 より前のサブリストから来ているため、減少するトリプレットではありません。

動的プログラミングまたはある種のメモ化を使用して、減少するトリプレットの数を数えようとしています。次のようにループ構造を設定するのは簡単です。

for i in xrange(0,len(L)-2):
    for j in xrange(i+1, len(L)-1):
        for k in xrange(j+1, len(L)):
            for item1 in L[i]:
                for item2 in L[j]:
                    if item1>item2:
                        for item3 in L[k]:
                            if item2>item3:
                                count+=1

ただし、より大きなリストにはあまりうまくスケーリングしません。リストを1回調べてトリプレットをカウントする方法が必要だと思います。たとえば、ある数値が別の数値よりも大きいことがわかっている場合 (または、それよりも大きい数値がいくつあるかわかっている場合)、後でその情報を再利用できるはずだと思います。

たとえば、有効なトリプレットでは、16 が 7 または 1 の前に来ることがあります。それが2つの「ペア」です。したがって、リストをさかのぼってトリプレットを作成しようとしていて、たとえば 19 を見ると、「これは 16 よりも大きいので、これから 2 つのトリプレットを作成できます。 16 は 2 より大きい数です。」等々。

大声で考えているだけですが、洞察をいただければ幸いです。

4

2 に答える 2

0

次のitertoolソリューションを試してください

import itertools
import time

L= [
    {19, 18, 14, 9, 4},
    {15, 12, 11, 10, 6, 5},
    {8},
    {16, 13, 3, 2},
    {17, 7, 1},
]


start = time.time()
for i in xrange(20000):
    count = 0
    for i in xrange(0,len(L)-2):
        for j in xrange(i+1, len(L)-1):
            for k in xrange(j+1, len(L)):
                for item1 in L[i]:
                    for item2 in L[j]:
                        if item1>item2:
                            for item3 in L[k]:
                                if item2>item3:
                                    count+=1

print
print time.time() - start

# result: 3.1542930603

start = time.time()
for i in xrange(20000):
    sum(1 for l1, l2, l3 in itertools.combinations(L, 3) for a, b, c in itertools.product(l1, l2, l3) if a > b > c)

print
print time.time() - start

# result: 1.94973897934
于 2012-04-13T20:01:35.207 に答える
0

ネストされたループの代わりにandのi間のインデックスを使用します。現在のトリプレットの最後の要素を追跡します。そして、メモを使って効率化しましょう。0n

L=[[19,18,14,9,4],[15,12,11,10,6,5],[8],[16,13,3,2],[17,7,1]]

n=len(L)

memo = {}
def f(i,j,last):
  if (i,j,last) in memo:
    return memo[(i,j,last)]
  if j==3:
    return 1
  if i==n:
    return 0
  res=0
  # take one from L[i]
  for x in L[i]:
    if last > x:
      res+=f(i+1,j+1,x)
  # don't take any element from L[i]
  res += f(i+1,j,last)
  memo[(i,j,last)] = res
  return res

BIG = 10**9
print f(0,0,BIG)
于 2012-04-13T20:11:29.647 に答える