字符串的C ++递归置换算法>不跳过重复 [英] C++ recursive permutation algorithm for strings -> not skipping duplicates

问题描述

我无法找到一个简单的语句来跳过这个递归排列代码的重复。我看到无处不在，似乎只找到使用交换或java的例子。从我收集的，我想我需要在for循环后立即生效。

谢谢！

  #includegenlib.h
 #includesimpio.h
 #include< string& 
 #include< iostream> 
 
 void ListPermutations（string prefix，string rest）; 
 
 
 int main（）{
 
 cout<< 输入一些字母以列出排列：; 
 string str = GetLine（）; 
 cout<< endl 排列是：<< endl 
 ListPermutations（，str）; 
 
 return 0; 
} 
 
 void ListPermutations（string prefix，string rest）
 {
 if（rest ==）
 {
 cout ;&前缀<< endl 
} 
 else 
 {
 for（int i = 0; i  {
 if =&&！prefix [i]）继续; //< ---我试过添加这个，但它不工作
 cout<< endl<< prefix：<前缀<< | rest：<休息< endl 
 string newPrefix = prefix + rest [i]; 
 string newRest = rest.substr（0，i）+ rest.substr（i + 1）; 
 ListPermutations（newPrefix，newRest）; 
} 
} 
} 
  

解决方案>

这应该工作：
你的算法是好的，我只添加了一个测试：如果一个唯一的字符已经在一个位置使用。如果是的话，不会进行更多的排列，因为所有在该位置的char的排列已经生成。

  void ListPermutations ，string rest）
 {
 if（rest ==）
 {
 cout<前缀<< endl 
} 
 else 
 {
 for（int i = 0; i  {
 
 
 // test if rest [i]是唯一的。 
 bool found = false; 
 for（int j = 0; j  {
 if（rest [j] == rest [i]）
 found = true; 
} 
 if（found）
继续; 
 string newPrefix = prefix + rest [i]; 
 string newRest = rest.substr（0，i）+ rest.substr（i + 1）; 
 ListPermutations（newPrefix，newRest）; 
} 
} 
} 
  

在进行置换之前，结果将是相同的。

I'm having trouble finding a simple statement to skip the duplicates for this recursive permutation code. I've looked everywhere and seem to only find examples using swap or java. From what I gather, I think I need to put a line right after the for-loop.

Thank you!

#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);           
        }    
    }
}

解决方案

this should work : your algoithm is good, i only added a test : if a unique char is already used at a position. if yes, no more permutation is made because all permutations with that char in that position is already made.

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);           
    }    
}
}

you can also sort the string before making permutations, the result will be the same.

这篇关于字符串的C ++递归置换算法>不跳过重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！