字母表多达29个字符的每一个排列？

StackOverflow https://stackoverflow.com/questions/4610093

题

我试图写一个程序，将产生与一个字符组成字母的每一种可能的排列文本文件29个字符。我选择29作为最长的英文单词，每个人都知道是反政教分离运动其长度为28个字符。有较长的，但主要是技术性很强的和模糊的。

我知道这会产生串的数量巨大。但是我不知道从哪里开始，甚至如何找出有多少这样的组合将产生。

答案请在PHP，处理，C ++或Java（I解决方案“M只有熟悉这些，PHP是首选，但可能没有最好的为了这个，我应该想象）。

或者甚至只是伪码/想法将不胜感激。

此外，有人说，这之前，这不是暴力破解或类似的东西。我是一个艺术家，尽管有些未知的，与我的概念混淆。

有帮助吗？

解决方案

词“置换”通常意味着每个字母都显示正好一次，所以这将是不可能的，以产生具有26个以上字母任何置换。无论如何，因为生成的字符串的数目太大，则可以使用随机串代替（以下是C代码）：

char s[30];
int p;
for (;;) // repeat forever: you cannot use a realistic iteration limit anyway
{
    for (p = 0; p < 29; ++p)
        s[p] = 'a' + rand() % 26;
    s[29] = '\0';
    puts(s);
}

其他提示

void out_perms(std::string word) {
    std::vector<int> indexes(word.size());
    for (size_t i = 0; i < indexes.size(); ++i)
        indexes[i] = i;
    do {
        for (size_t i = 0; i < indexes.size(); ++i)
            std::cout << word[indexes[i]];
        std::cout << std::endl;
    } while (std::next_permutation(indexes.begin(), indexes.end()));
}

int main(int, char**) {
    out_perms("asdfg");
}

请参阅 http://codepad.org/6lQTPQrG 例如输出

显然，对于环外是字符在字的数量。然后，您只需创建与长度的字符串。对于长度为5，则开始与 “AAAAA”，然后 “AAAAB”， “AAAAC”。

一旦你点击“Z”，你回去角色移动到左边一上来，即“AAAAZ”变成“AAABA”和“AAAZZ”变成“AABAA”。一旦你点击“ZZZZZ”，你与内循环中完成，然后外环将与“AAAAAA”启动。

下面是在C ++中的简单程序未经测试，通过计数在基座26创建的话：

#include <string>
#include <iostream>

int main(void)
{
    //----------------------------------------------------------
    //  Print permuations of strings of letters up to length 5.
    //  Use base 26 arithmetic.
    //----------------------------------------------------------
    const unsigned int MAX_ITERATIONS = 26 * 26 * 26 * 26 * 26;

    std::string word = "A";
    for (unsigned int i = 0; i < MAX_ITERATIONS; ++i)
    {
        //------------------------------------------------------
        //  Print the word
        //------------------------------------------------------
        std::cout << word << std::endl;

        //------------------------------------------------------
        //  Increment the word, using base 26 arithmetic.
        //  A, B, C, ..., Z.
        //  AA, BA, CA, ..., ZA, AB, BB, CB, DB, ..., ZZ.
        //  AAA, BAA, CAA, ..., ZAA, ABA, BBA, CBA, DBA, ..., ZZZ.
        //------------------------------------------------------
        bool            carry_generated = false;
        unsigned int    digit = 0;
        do
        {
            carry_generated = false;
            if (word[digit] < 'Z')
            {
                ++word[digit];
                break;
            }
            word[digit++] = 'A';
            if (word.length() == digit)
            {
                word += "A";
                break;
            }
            carry_generated = true;
        } while (carry_generated && (digit < 5));
    }

    return 0;
}

可以通过检查打印前一个词列表（也称为字典）可以减少打印的字的数量。如果单词的单词列表，打印。

<强>使用的29字长代表着量的最大的问题。量溢出标准C ++无符号整数的范围内。 A 大诠释库将需要被使用。的的下一个问题是每个组合处理所需的时间。乘以每次迭代1微秒（一种更坏情况下）和向下降低到数天，小时，分钟和秒的数量。也许几年可能需要。

使用PHP的Perl样式的字符递增。

set_time_limit(0);

$perm = 'A';
$endTest = str_repeat('Z',28).'A';
while ($perm != $endTest) {
    echo $perm++,"\n";
}

从命令行，这样你就不会打了一个网络服务器超时脚本;然后守株待兔几年它完成

function p($length, $partial)
{
      if ($length == 0) return $partial;
      $ans = array();
      foreach (range('a', 'z') as $i)
      {
          $ans[] = p($length -1, $partial . $i);
      }
      return $ans;  
}

$top = 3;
//$f = fopen('out.txt');
for ($l = 1; $l < $top+1; $l++)
{
     print_r(p($l), '');
     //fwrite($p($l), '');
}

如果您要设置$top至29，并给它一个尝试继续。我不会去。

编辑 - print_r(p($l), ''); ---> print_r(p($l, ''));

PHP保持我留下深刻印象，其失误的宽容。缺少“必要”的说法我p？没问题ITLL只是空字符串以某种方式（或零，还是假的，根据情况）。第二个'参数print_r的？没有区别，被处理过的象缺省false反正

修改

我不知道我在做什么是地狱了这里。在不同的返回类型P的相当奇数，并且将返回的化合物阵列具有怪异结构。

这是一个更好的解决方案无论如何

$lengthDesired = 29;
for($i='a'; $i != str_pad('',$lengthDesired+1,'a'); $i++)
    echo $i .', ';

下面是用Java编写 http://www.merriampark.com/perm.htm一个置换生成器。

然而，因为他提到

  //-----------------------------------------------------------
  // Constructor. WARNING: Don't make n too large.
  // Recall that the number of permutations is n!
  // which can be very large, even when n is as small as 20 --
  // 20! = 2,432,902,008,176,640,000 and
  // 21! is too big to fit into a Java long, which is
  // why we use BigInteger instead.
  //----------------------------------------------------------

由于您的n是29，你会等待很长一段时间。它是太大，因为EboMike是想告诉你他的评论。

只是了我的头顶部（PHP）。

$index = 0;

while(1) {
   $output_string = '';
   $base_26 = (string)base_convert($index, 10, 26);
   if (strlen($base_26) > 29) break;
   for ($i = 0; $i < strlen($base_26); $i++) {
      $output_string .= chr(65 + base_convert($base_26[$i], 26, 10));
   }
   $index++;
   echo $output_string;
}

这是我会做什么：

#include <iostream>

void printWords(std::string& word, int index, int last)
{
    std::cout << word << "\n";
    if (index != last)
    {
        for(char loop = 'a'; loop <= 'z'; ++loop)
        {
            word[index] = loop;
            printWords(word, index+1, last);
        }
        word[index] = ' ';
    }
}

int main()
{
    std::string word("                             "); // 29 space

    printWords(word,0,word.length());
}

一个Java解决方案应该做的伎俩：

public void characterPermutations(int length, LinkedList<String> permutations) {
    if(length > 1) {
        characterPermutations(length - 1, permutations);

        ListIterator<String> iterator = permutations.listIterator();
        while(iterator.hasNext()) {
            String permutation = iterator.next();
            for(char c = 'a'; c <= 'z'; c++) {
                iterator.add(c + permutation);
            }
        }

    } else {
        for(char c = 'a'; c <= 'z'; c++) {
            permutations.add(c + "");
        }
    }
}

public class hii {  

public static void main(String[] args){

    String[] database = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};

    for(int i=1; i<=database.length; i++){
        String[] result = getAllLists(database, i);
        for(int j=0; j<result.length; j++){
            System.out.println(result[j]);
        }
    }



}


    public static String[] getAllLists(String[] elements, int lengthOfList)
    {
        //initialize our returned list with the number of elements calculated above
        String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

        //lists of length 1 are just the original elements
        if(lengthOfList == 1) return elements; 
        else {
            //the recursion--get all lists of length 3, length 2, all the way up to 1
            String[] allSublists = getAllLists(elements, lengthOfList - 1);

            //append the sublists to each element
            int arrayIndex = 0;

            for(int i = 0; i < elements.length; i++){
                for(int j = 0; j < allSublists.length; j++){
                    //add the newly appended combination to the list
                    allLists[arrayIndex] = elements[i] + allSublists[j];
                    arrayIndex++;
                }
            }
            return allLists;
        }
    }






}

我能想到的最简单的方法，从1焦炭到29个字符让每一个排列在伪代码：

loop from i = 1 to 26^29 or 27^29 if you want to include spaces
{
   convert i to base 26 or 27;
   translate each number to the corresponding letter;
}

即使你可以这样存储在磁盘上，像thirydot指出的那样，你的时间做这个用完了。

只需生成（和不存储）中的所有6个字母possiblilies把我的计算机24秒时：

$ time perl letters.pl

real    0m24.837s
user    0m24.765s
sys     0m0.030s

这是7.7X10 ^每字-8S，这意味着它会采取8.4×10 ^ -33或2.6×10 ^26年做到这一点。

您需要更多地考虑你的算法。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top