0

指定されたマトリックス（水平および垂直）で最も長く繰り返される文字を取得するPythonスクリプトを作成しようとしています。

例：

私はこのマトリックスを持っています:

afaaf
rbaca
rlaff

この行列を入力に与えると、結果は 3になります。

マトリックスの 3 列目は a でいっぱいで、マトリックスで最も繰り返される文字であることがわかります。

私が持っているもの：

#!/bin/python2.7

#Longest string in matrix

#Given a matrix filled with letters. Find the longest string, containing only the same letter, which can be obtained by starting
#with any position and then moving horizontally and vertically (each cell can be visited no more than 1 time).


# Settings here
# -------------
string_matrix = """
afaaf
rbaca
rlaff
"""

pos = (0,0)
# -------------

import pdb
import time
import collections
from collections import defaultdict
import re


rows = 0
columns = 0
matrix = []
matrix2 = []
counter = 0
res_l = []
i = 0
c = ''

# if matrix2 is full of 1's, stop
def stop():
    for i in range(0, rows):
        for j in range(0, columns):
            if matrix2[i][j] == 0:
                return False
    return True

# checks the points, and returns the most repeated char and length
def check_points(points1, points2):
    r = []

    r.append(-1)
    r.append('')

    # create strings from matrix
    s1 = ''
    s2 = ''


    for point in points1:
        s1 += matrix[point[0]][point[1]]

    for point in points2:
        s2 += matrix[point[0]][point[1]]

    rr = {}

    for c in s1:
        rr[c] = 0

    for c in s2:
        rr[c] = 0

    for i in range(0, len(s1)):
        k = 1
        for j in range(i+1, len(s1)):
            if s1[i] == s1[j]:
                k += 1
            else:
                break
            if k > rr[s1[i]]:
                rr[s1[i]] = k


    for i in range(0, len(s2)):
        k = 1
        for j in range(i+1, len(s2)):
            if s2[i] == s2[j]:
                k += 1
            else:
                break
            if k > rr[s2[i]]:
                rr[s2[i]] = k


    m = -1
    c = ''
    for key,value in rr.iteritems():
        if value > m:
            m = value
            c = key

    return m, c


# Depth-first search, recursive
def search(pos):
    global res_l
    global matrix2
    global c

    counter = 0

    x = pos[0]
    y = pos[1]

    c = matrix[x][y]

    # base clause
    # when matrix2 is all checked
    if stop():
        return counter, c



    points1 = []
    points2 = []
    allpoints = []

    for i in range(0, columns):
            if matrix2[x][i] != 1:
                points1.append([x, i])
                allpoints.append([x, i])


    for i in range(0, rows):
            if matrix2[i][x] != 1:
                points2.append([i, x])
                allpoints.append([i, x])





    r = check_points(points1, points2)


    if r[0] > counter:
        counter = r[0]
        c = r[1]

    matrix2[x][y] = 1


    for point in allpoints:
        rr = search(point)
        if rr[0] > counter:
            counter = int(rr[0])
            c = rr[1]
            #print 'c: ' + str(c) + ' - k: ' + str(counter)



    return counter, c

def main():
    # create the matrix from string
    string_matrix_l = string_matrix.strip()
    splited = string_matrix_l.split('\n')


    global rows
    global columns
    global matrix
    global matrix2

    rows = len(splited)
    columns = len(splited[1])



    # initialize matrixes with 0
    matrix = [[0 for x in range(columns)] for x in range(rows)]
    matrix2 = [[0 for x in range(columns)] for x in range(rows)]


    # string to matrix
    i = 0
    for s in splited:
        s = s.strip()
        if s == '':
            continue

        j = 0

        for c in s:
            try:## Heading ##
                matrix[i][j] = c
                #print 'ok: ' + str(i) + ' ' + str(j) + ' ' +  c
            except:
                print 'fail: index out of range matrix[' + str(i) + '][' + str(j)+'] ' + c
            j = j + 1

        i = i + 1


    # print some info
    print 'Given matrix: ' + str(matrix) + '\n'
    print 'Start position: ' + str(pos)
    print 'Start character: ' + str(matrix[pos[0]][pos[1]])

    # get the result
    res = search(pos)
    print '-------------------------------------'
    print '\nChar: ' + str(res[1]) + '\nLength: ' + str(res[0])


if __name__ == "__main__":
    main()

これは私のソースコードです。上記の例は、ソース コードでも使用されています。与えられた結果は次のとおりです: r 2これは間違っています ... 繰り返しますが、3である必要があります

main、search、stop、check_points の 4 つの機能があります。

  • メインは物事を初期化することです、
  • search は、1 つのパラメーター (開始点) を受け取る再帰関数であり、最も長い文字列を再帰的にチェックする必要があります。元と同じ長さの別の行列があります。これはちょうど 1 と 0 です。1 はその位置が訪問されたことを意味し、0 ではありません。検索機能は、特定の位置が検索機能によって処理された後、右側の位置に 1 を設定します。
  • stop は、matrix2 が 1 でいっぱいかどうかをチェックしています。この場合、行列はすべて解析されました。
  • check_points は 2 つのパラメーター、2 つのポイントのリストを取り、最も繰り返される文字とそれらのポイントの長さを返します

機能しないもの:

ほとんどの場合、結果として間違った文字が表示されますが、カウントが正しい場合もあります。水平方向に動作する場合もあれば、そうでない場合もあります。私は何か間違ったことをしていると確信していますが...これを行う方法を見つけようとしてから1週間以上経ちました。ここで、stackoverflow で別の質問をしましたが、もう少し進みましたが、まだスタックしています。

どんな提案でも大歓迎です。

4

2 に答える 2

2

を使用itertools.groupbyして、特定の文字の繰り返し回数をすばやく見つけたりizip_longest(*matrix)、行列を転置したり (行と列を入れ替えたり) できます。

from itertools import groupby, izip_longest

matrix_string = """
afaaf
rbaca
rlaff
"""

def longest_repetition(row): 
    return max((sum(1 for item in group), letter) 
               for letter, group in groupby(row) 
               if letter is not None)

def main():
    matrix = [[letter for letter in row.strip()] 
              for row in matrix_string.strip().split('\n')]

    count, letter = max(
        max(longest_repetition(row) for row in matrix),
        max(longest_repetition(col) for col in izip_longest(*matrix))
    )

    print letter, count

if __name__ == '__main__':
    main()

要件を更新したので、ここにコードの再帰バージョンといくつかの説明があります。それが割り当てではなく、このタスクが実際の問題で発生した場合は、最初のバージョンを使用する必要がありました。

matrix_string = """
afaaf
rbaca
rlaff
"""


def find_longest_repetition(matrix):
    rows = len(matrix)
    cols = len(matrix[0])

    # row, col - row and column of the current character.
    # direction - 'h' if we are searching for repetitions in horizontal direction (i.e., in a row).
    #             'v' if we are searching in vertical direction.
    # result - (count, letter) of the longest repetition we have seen by now.
    #          This order allows to compare results directly and use `max` to get the better one
    # current - (count, letter) of the repetition we have seen just before the current character.
    def recurse(row, col, direction, result, current=(0, None)):
        # Check if we need to start a new row, new column, 
        #   new direction, or finish the recursion.
        if direction == 'h':    # If we are moving horizontally
            if row >= rows:     # ...  and finished all rows
                return recurse( # restart from the (0, 0) position in vertical direction.
                    0, 0,
                    'v',
                    result
                )
            if col >= cols:     # ... and finished all columns in the current row
                return recurse( # start the next row.
                    row + 1, 0,
                    direction,
                    result
                )
        else:                   # If we are moving vertically
            if col >= cols:     # ... and finished all columns
                return result   # then we have analysed all possible repetitions. 
            if row >= rows:     # ... and finished all rows in the current column
                return recurse( # start the next column.
                    0, col + 1,
                    direction,
                    result
                )

        # Figure out where to go next in the current direction
        d_row, d_col = (0, 1) if direction == 'h' else (1, 0)

        # Try to add current character to the current repetition
        count, letter = current
        if matrix[row][col] == letter:
            updated_current = count + 1, letter
        else:
            updated_current = 1, matrix[row][col]

        # Go on with the next character in the current direction
        return recurse( 
            row + d_row, 
            col + d_col,
            direction,
            max(updated_current, result), # Update the result, if necessary
            updated_current
        )

    return recurse(0, 0, 'h', (0, None))


def main():
    matrix = [[letter for letter in row.strip()] 
              for row in matrix_string.strip().split('\n')]

    count, letter = find_longest_repetition(matrix)

    print letter, count


if __name__ == '__main__':
    main()
于 2015-04-08T09:05:59.400 に答える
1

collections.Counter(string).most_common()を試して、文字の繰り返しを最大限に取得することもできます。

from collections import Counter

string_matrix = """
afaaf
rbaca
rlaff
"""

def GetMostRepetitions(pos):
    mc = []

    for ii in range(pos[0],len(working_mat)):
        mc.extend(Counter(working_mat[ii]).most_common(1))  

        for jj in range(pos[1],len(working_mat[0])):
            column = []           

            for kk in range(ii,len(working_mat)):
                column.append(working_mat[kk][jj])

            mc.extend(Counter(column).most_common(1))          

    m = 0           
    for item in mc: 
        if item[1] > m:
            m = item[1]
            k = item[0]


    print(k, m)                 

working_mat = string_matrix.strip().split('\n')

for ii in range(len(working_mat)):
    for jj in range(len(working_mat[0])):
        pos = (ii,jj)
        GetMostRepetitions(pos)

コルマーが言ったように、より良い方法で行列を転置することもできます。

于 2015-04-08T09:24:58.163 に答える