5

このアルゴリズムは、しばらくの間私を逃れてきました。文字列「cccaatt」が与えられたとしましょう。繰り返される文字の各部分文字列の可能なすべてのバリエーションを生成しようとしています。EG、入力として「cccaatt」を返すと、次のようになります。

猫、猫、caat、caatt、ccat、ccatt、ccaat、ccaatt、cccat、cccatt、cccaat、cccaatt

結果がすべて返される限り、結果の順序は重要ではありません。一般に、入力は文字列であり、各グループは k_n 文字の長さで、繰り返される文字の g グループで構成されます。

私の直感では、これは再帰的なアルゴリズムですが、その正確な構造を理解するのは困難でした。

4

3 に答える 3

2

アルファベットと各文字の最大出現回数を保存する場合（コメントで素晴らしく言及されているように）、これを行うことができます：

function variations(letter_type, current string) {
    if (letter_type is in the alphabet) {
        while (string has fewer than the max amount of that letter) {
            add one of that letter to current string
            variations(next letter, current string)
        }
    } else {
        print current string // since there are no more letters to add
    }
}

Java の場合:

public class Variations {

    static String[] alphabet = {"c","a","t"};
    static int[] maximums = {3, 2, 2};

    public static void main(String[] args) {
        variations(0, "");
    }

    public static void variations(int letter_type, String curr) {
        if (letter_type < alphabet.length) {
            for (int i = 1; i <= maximums[letter_type]; i++) {
            curr += alphabet[letter_type];
            variations(letter_type+1, curr);
            }
        } else {
            System.out.println(curr);
        } 
    }

}
于 2012-09-05T07:42:52.737 に答える
1

Python itertools モジュールには、次のプログラムにつながるグループのメンバーをグループ化して反復処理するための強力なツールがあります。

いくつかの中間結果を示し、pprint モジュールを使用して答えを整形しました。

Python 2.7.3 (default, Aug  1 2012, 05:16:07) 
[GCC 4.6.3] on linux2
Type "copyright", "credits" or "license()" for more information.
>>> import itertools
>>> instring = "cccaatt"
>>> [(x[0], list(x[1])) for x in itertools.groupby(instring)]
[('c', ['c', 'c', 'c']), ('a', ['a', 'a']), ('t', ['t', 't'])]
>>> xx = [list(x[0]*n for n in range(1, len(list(x[1]))+1)) for x in itertools.groupby(instring)]
>>> xx
[['c', 'cc', 'ccc'], ['a', 'aa'], ['t', 'tt']]
>>> list(itertools.product(*xx))
[('c', 'a', 't'), ('c', 'a', 'tt'), ('c', 'aa', 't'), ('c', 'aa', 'tt'), ('cc', 'a', 't'), ('cc', 'a', 'tt'), ('cc', 'aa', 't'), ('cc', 'aa', 'tt'), ('ccc', 'a', 't'), ('ccc', 'a', 'tt'), ('ccc', 'aa', 't'), ('ccc', 'aa', 'tt')]
>>> from pprint import pprint as pp
>>> pp(list(itertools.product(*xx)))
[('c', 'a', 't'),
 ('c', 'a', 'tt'),
 ('c', 'aa', 't'),
 ('c', 'aa', 'tt'),
 ('cc', 'a', 't'),
 ('cc', 'a', 'tt'),
 ('cc', 'aa', 't'),
 ('cc', 'aa', 'tt'),
 ('ccc', 'a', 't'),
 ('ccc', 'a', 'tt'),
 ('ccc', 'aa', 't'),
 ('ccc', 'aa', 'tt')]
>>>

または関数として：

>>> def stringexpand(instring):
    xx = [list(x[0]*n for n in range(1, len(list(x[1]))+1)) for x in itertools.groupby(instring)]
    return list(itertools.product(*xx))

>>> pp(stringexpand("cccaatt"))
[('c', 'a', 't'),
 ('c', 'a', 'tt'),
 ('c', 'aa', 't'),
 ('c', 'aa', 'tt'),
 ('cc', 'a', 't'),
 ('cc', 'a', 'tt'),
 ('cc', 'aa', 't'),
 ('cc', 'aa', 'tt'),
 ('ccc', 'a', 't'),
 ('ccc', 'a', 'tt'),
 ('ccc', 'aa', 't'),
 ('ccc', 'aa', 'tt')]
>>>

部品から結合された文字列が必要なようです。これは、このわずかな mod で実行できます。

def stringexpand(instring):
    xx = [list(x[0]*n for n in range(1, len(list(x[1]))+1)) for x in itertools.groupby(instring)]
    return [''.join(parts) for parts in itertools.product(*xx)]

どちらが返されますか:

['cat',
 'catt',
 'caat',
 'caatt',
 'ccat',
 'ccatt',
 'ccaat',
 'ccaatt',
 'cccat',
 'cccatt',
 'cccaat',
 'cccaatt']
于 2012-09-05T19:26:52.407 に答える
1

文字列を数字と繰り返し回数のリストに分解します。つまり、"cccaatt" => [(c,3), (a,2), (t,2)] です。問題は再帰的に定義できます。

Let xs = [(a_1, n_1), (a_2, n_2), (a_3, n_3), ... (a_k, n_k)]
define Perm(xs):
    if len(xs) == 1:
        return all length variations of xs
    else:
        return every sequence in Perm(x[:-1]) appended with one or more from x[-1]

すぐにPythonの例があります。

> perm("cccaatt")
> ['cat', 'ccat', 'cccat', 'caat', 'ccaat', 'cccaat', 'catt', 'ccatt', 'cccatt', 'caatt', 'ccaatt', 'cccaatt']

コード添付

def perm(xs):
    if not xs:
        return []

    # group them into the correct format, probably should have used groupby + zip
    l = [(xs[0],1)]
    for x in xs[1:]:
        last, num = l[-1]
        if last == x:
            l[-1] = (last, num+1)
        else:
            l.append((x, 1))

    # print(l)
    print(recurse(l))

# this is where the real work is done.
def recurse(xs):
    if len(xs) == 1:
        return [ xs[0][0] * x for x in range(1, xs[0][1] + 1) ]

    prev = recurse(xs[:-1])
    char, num = xs[-1]
    return [ y + x * char for x in range(1,num + 1) for y in prev ]
于 2012-09-05T05:29:50.817 に答える