字符串的C递归置换算法 – >不跳过重复

发布时间：2020-12-16 10:30:20 所属栏目：百科来源：网络整理

导读：我很难找到一个简单的语句来跳过这个递归排列代码的重复项.我到处看,似乎只找到使用swap或 java的例子.从我收集的内容来看,我认为我需要在for-loop之后放一条线. 谢谢！ #include "genlib.h"#include "simpio.h"#include string#include iostreamvoid ListPe

我很难找到一个简单的语句来跳过这个递归排列代码的重复项.我到处看,似乎只找到使用swap或 java的例子.从我收集的内容来看,我认为我需要在for-loop之后放一条线.

谢谢！

#include "genlib.h"
#include "simpio.h"
#include <string>
#include <iostream>

void ListPermutations(string prefix,string rest);


int main() {

    cout << "Enter some letters to list permutations: ";
    string str = GetLine();
    cout << endl << "The permutations are: " << endl;
    ListPermutations("",str);

    return 0;
}

void ListPermutations(string prefix,string rest)
{
    if (rest == "") 
    {
        cout << prefix << endl;
    } 
    else 
    {   
        for (int i = 0; i < rest.length(); i++) 
        {
            if (prefix != "" && !prefix[i]) continue; // <--- I tried adding this,but it doesn't work
            cout << endl<< "prefix: " << prefix << " | rest: " << rest << endl;     
            string newPrefix = prefix + rest[i];
            string newRest = rest.substr(0,i) + rest.substr(i+1);  
            ListPermutations(newPrefix,newRest);           
        }    
    }
}

解决方法

这应该工作：
你的算法是好的,我只添加了一个测试：如果一个位置已经使用了一个独特的字符.如果是,则不再进行排列,因为已经在该位置使用该字符的所有排列.

void ListPermutations(string prefix,string rest)
{
if (rest == "") 
{
    cout << prefix << endl;
} 
else 
{   
    for (int i = 0; i < rest.length(); i++) 
    {


        //test if rest[i] is unique.
        bool found = false;
        for (int j = 0; j < i; j++) 
        {
            if (rest[j] == rest[i])
                found = true;
        }
        if(found)
            continue;
        string newPrefix = prefix + rest[i];
        string newRest = rest.substr(0,i) + rest.substr(i+1);  
        ListPermutations(newPrefix,newRest);           
    }    
}
}

您也可以在进行排列之前对字符串进行排序,结果将是相同的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

字符串的C递归置换算法 – &gt;不跳过重复

解决方法

字符串的C递归置换算法 – >不跳过重复