6

我有形式的字符串000011122222。也就是说，连续的数字重复随机数。次。其他一些例子可能是：

0011122223333
01222    
00011234444
001122222

等等。我知道，对于 string01222来说，总共5!/3!可能有排列。我需要为每个这样的字符串生成所有这些排列。

我尝试过通过各种方法生成排列。一种是生成所有可能的排列（就像没有重复的字符串一样），但是由于我将使用的字符串可能非常大，这可能会浪费时间来生成过多的冗余排列。

其次，我尝试将数字放置在等于字符串大小的字符数组的随机索引处，并在数字计数与输入字符串中的相同时终止循环。但是，这样我浪费了很多内存，也占用了很多时间。

我需要一种有效的方法来为这些字符串生成排列。只是一个算法或代码，任何一个都是受欢迎的。我正在使用 Java。

谢谢！

4

4 回答 4

7

生成排列的标准算法之一是按字典顺序排列排列的算法。该算法被 C++ 算法的大多数实现所使用，最多std::next_permutation在 O(n) 时间排列中生成排列，并跳过所有相互重复的排列。它也非常容易编码。

希望这可以帮助！

于 2012-07-04T20:02:18.107 回答
3

不是置换原始数字字符串，而是置换数字组。我不知道如何最好地描述它，所以我会尝试一些伪代码。

对于字符串“001222”，数字组是两个 0、一个 1 和三个 2。

permute(groups, permutation):
    if there are no non-empty groups
        print permutation
    else
        for each non-empty group
            permutation += group.digit
            --group.count
            permute(groups, permutation)

通过循环组而不是所有数字，它可以避免生成重复，因为每个数字只能为下一个位置选择一次，而不是多次。遍历你得到的随机排列

Permutation  Digit Groups

             0: 2, 1: 1, 2: 3  // start
0            0: 1, 1: 1, 2: 3
02           0: 1, 1: 1, 2: 2  // *
021          0: 1, 1: 0, 2: 2  // the 1 group is removed from the set
0212         0: 1, 1: 0, 2: 1
02120        0: 0, 1: 0, 2: 1  // the 0 group is removed from the set
021202       0: 0, 1: 0, 2: 0  // the 2 group is removed from the set

现在展开回 *.

02           0: 1, 1: 0, 2: 1

因为您循环的是数字组而不是原始字符串中的所有（重复）数字，所以您不能再次选择 2。这意味着所有以“02”开头的排列都是唯一的，因为前缀“02”只生成一次。这同样适用于整个算法。

更新

这是一个快速的 PHP 实现，它为输入“001222”产生 60 个排列：

function permute(&$groups, &$count, $permutation) {
    $done = true;
    foreach ($groups as &$group) {
        if ($group[1] > 0) {
            --$group[1];
            permute($groups, $count, $permutation . $group[0]);
            ++$group[1];
            $done = false;
        }
    }       
    if ($done) {
        echo $permutation . PHP_EOL;
        ++$count;
    }
}

$groups = array(
    array(0, 2),
    array(1, 1),
    array(2, 3),
);
$count = 0;
permute($groups, $count, '');
echo "\nTotal: $count\n";
于 2012-07-04T20:24:21.010 回答
0

您可以通过随机选择位数来创建字符串。像这样：

length : int - Total string length
digits : int - maximum digit to include in the string
string : String - the return value
for(i : int from 0 to digits)
{
    remainingChars : int = length - length(string) //remaining chars in string
    remainingDigits : int = digits - i + 1
    count : int = Random from 1 to (remainingChars - remainingDigits + 1)
    Append count times i to the string
}
于 2012-07-04T20:09:52.687 回答
0

我不知道你到底想说什么，但我曾经需要一个排列版本，其中我有一组像 012 这样的数字，所有排列都是：

012 021 102 120 201 210

为了实现这一点，我在维基百科http://en.wikipedia.org/wiki/Permutation 上查找了算法，然后我为它创建了一个方法，如下所示：

    public static boolean Permute(int[] a) {
        int k, l, n = a.length -1;
        for (k = n -1; ; k--) {
            if (k == -1)
                return false;
            if (a[k] < a[k + 1])
                break;
        }
        for (l = n; l >= 0; l--) {
            if (a[k] < a[l]) {
                int opt = a[l];
                a[l] = a[k];
                a[k] = opt;
                break;
            }
        }
        for (int i = k + 1, j = n; i < j; i++, j--) {
            int opt = a[i];
            a[i] = a[j];
            a[j] = opt;
        }
        return true;
    }

如果您更具体，我可以帮助您

于 2012-07-04T20:19:32.153 回答