2

n と k の 2 つの int を受け取るアルゴリズムを実装しようとしています。ここで、n は列の座席数、k はその列に座ろうとする学生の数です。問題は、各生徒が両側で少なくとも2席離れている必要があるということです。私が持っているのは、すべてのサブセット (0 または 1 の配列、1 は誰かがそこに座っていることを意味する) を生成する関数であり、これを関数に送信して、有効なサブセットであるかどうかを確認します。これは私がその機能のために持っているコードです

def process(a,num,n):
    c = a.count('1')
    #If the number of students sitting down (1s) is equal to the number k, check the subset
    if(c == num):
        printa = True
        for i in range(0,n):
            if(a[i] == '1'):
                if(i == 0):
                    if( (a[i+1] == '0') and (a[i+2] == '0') ):
                        break
                    else:
                        printa = False
                elif(i == 1):
                    if( (a[i-1] == '0') and (a[i+1] == '0') and (a[i+2] == '0') ):
                        break
                    else:
                        printa = False
                elif(i == (n-1)):
                    if( (a[i-2] == '0') and (a[i-1] == '0') and (a[i+1] == '0') ):
                        break
                    else:
                        printa = False
                elif(i == n):
                    if( (a[i-2] == '0') and (a[i-1] == '0') ):
                        break
                else:
                    printa = False                    
            else:
                if( (a[i-2] == '0') and (a[i-1] == '0') and (a[i+1] == '0') and (a[i+2] == '0') ):
                    break
                else:
                    printa = False
        if(printa):
            print a
    else:
        return

コードは k と n の小さな入力に対して機能しますが、より高い値を取得すると、何らかの理由でインデックスからリストエラーが発生します。
どんな助けにも感謝します。

O 入力 a は、次のようなリストです

['1','0','0','1','0'] # a valid subset for n=5 and k=2
['0','0','0','1','1'] # an invalid subset

編集：

プロセスを呼び出すコード:

'''
This function will recursivly call itself until it gets down to the leaves then sends that
subset to process function.  It appends
either a 0 or 1 then calls itself
'''
def seatrec(arr,i,n,k):
    if(i==n):
        process(arr,k,n)
        return
    else:
        arr.append("0")
        seatrec(arr,i+1,n,k)
        arr.pop()
        arr.append("1")
        seatrec(arr,i+1,n,k)
        arr.pop()
    return
'''
This is the starter function that sets up the recursive calls
'''
def seat(n,k):
    q=[]
    seat(q,0,n,k)

def main():
    n=7
    k=3
    seat(n,k)

if __name__ == "__main__":
    main()

これらの数値を使用すると発生するエラーは次のとおりです。

if( (a[i-2] == '0') and (a[i-1] == '0') and (a[i+1] == '0') ):
IndexError: list index out of range
4

2 に答える 2

3

無効な座席配置を除外するだけで十分です。つまり、生徒が隣り合って座っている場合、['1', '1']または生徒の間に 1 席しかない場合、正しい数の、および有効な['1', '0', '1']他のすべての配置を除外するだけで十分です。例:'1''0'

def isvalid(a, n, k):
    if not isinstance(a, basestring):
       a = ''.join(a) # `a` is a list of '1', '0'
    return (len(a) == n and a.count('1') == k and a.count('0') == (n-k) and
            all(p not in a for p in ['11', '101']))

すべてのサブセットをチェックせずに有効なサブセットを生成する、より効率的なアルゴリズムがあります。

def subsets(n, k):
    assert k >= 0 and n >= 0
    if k == 0: # no students, all seats are empty
        yield '0'*n
    elif k == 1 and (n == 1 or n == 2): # the last student at the end of the row
        yield '1' + '0'*(n-1) # either '1' or '10'
        if n == 2: yield '01'
    elif n > 3*(k-1): # there are enough empty seats left for k students
        for s in subsets(n-3, k-1):
            yield '100' + s # place a student
        for s in subsets(n-1, k):
            yield '0' + s   # add empty seat

例

n, k = 5, 2
for s in subsets(n, k):
    assert isvalid(s, n, k)
    print(s)

出力

10010
10001
01001
于 2012-02-17T07:45:34.527 に答える
2

長さの配列のインデックスnは0～n-1です。したがって、アクセスnはリスト外です。

小さい値でこれに気付いていない場合は、リストを生成するコードにバグがあるに違いありません。

于 2012-02-17T06:46:23.280 に答える