我如何才能找到一个字符串的所有排列不使用递归？ [英] How can I find all permutations of a string without using recursion?

问题描述

有人可以帮助我：这是一个程序找到任何长度的字符串的所有排列。需要的相同的非递归形式。 （C语言实现是preferred）

 使用名字空间std;

串动开关（字符串topermute，诠释的x，int y）对
{
  字符串newstring = topermute;
  newstring [X] = newstring [Y]
  newstring [Y] = topermute [X] //避免临时变量
  返回newstring;
}

无效置换（字符串topermute，INT的地方）
{
  如果（地方== topermute.length（） -  1）
  {
    COUT＆LT;＆LT; topermute＆LT;＆LT; ENDL;
  }
  对于（INT nextchar =到位; nextchar＆LT; topermute.length（）; nextchar ++）
  {
    置换（动开关（topermute，地点，nextchar），地点+ 1）;
  }
}

INT主（INT ARGC，字符* argv的[]）
{
  如果（的argc！= 2）
  {
    COUT＆LT;＆LT;正确输入为置换字符串';
    返回1;
  }
  置换（的argv [1]，0）;
  返回0;
}
 

解决方案

你的code一个基于堆栈的非递归等价的：

 的#include＆LT;的iostream＆GT;
＃包括＆LT;字符串＆GT;

结构状态
{
    国家（标准::字符串topermute_，INT place_，INT nextchar_，国* next_ = 0）
        ：topermute（topermute_）
        ，地点（place_）
        ，nextchar（nextchar_）
        ，下一个（next_）
    {
    }

    标准::字符串topermute;
    诠释到位;
    INT nextchar;

    国*接下来的;
};

标准::字符串动开关（标准::字符串topermute，诠释的x，int y）对
{
    标准::字符串newstring = topermute;
    newstring [X] = newstring [Y]
    newstring [Y] = topermute [X] //避免临时变量

    返回newstring;
}

无效置换（标准::字符串topermute，诠释到位= 0）
{
    //链表栈。
    国家*顶部=新的国家（topermute，地点，地点）;

    而（顶！= 0）
    {
        国家*弹出=顶部;
        TOP =弹出＆gt;接着，

        如果（弹出＆GT;地方==弹出＆GT; topermute.length（） -  1）
        {
            性病::法院＆LT;＆LT;弹出＆GT; topermute＆LT;＆LT;的std :: ENDL;
        }

        对于（INT I =弹出＆GT;的地方;我＆LT;弹出＆GT; topermute.length（）; ++ I）
        {
            顶部=新的国家（动开关（弹出＆GT; topermute，弹出＆GT;的地方，我），弹出＆GT;地方+ 1，我，顶）;
        }

        删除弹出;
    }
}

INT主（INT ARGC，字符* argv的[]）
{
    如果（的argc！= 2）
    {
        性病::法院＆LT;＆LT;正确输入为置换字符串';
        返回1;
    }
    其他
    {
        置换（的argv [1]）;
    }

    返回0;
}
 

我试图让C风格，避免了C ++ STL容器和成员函数（用于虽然为简单起见构造函数）。

请注意，以相反的顺序产生为原始的排列。

我要补充一点，以这种方式使用堆栈只是模拟递归。

Can someone help me with this: This is a program to find all the permutations of a string of any length. Need a non-recursive form of the same. ( a C language implementation is preferred)

using namespace std;

string swtch(string topermute, int x, int y)
{
  string newstring = topermute;
  newstring[x] = newstring[y];
  newstring[y] = topermute[x]; //avoids temp variable
  return newstring;
}

void permute(string topermute, int place)
{
  if(place == topermute.length() - 1)
  {
    cout<<topermute<<endl;
  }
  for(int nextchar = place; nextchar < topermute.length(); nextchar++)
  {
    permute(swtch(topermute, place, nextchar),place+1);
  }
}

int main(int argc, char* argv[])
{    
  if(argc!=2)    
  {
    cout<<"Proper input is 'permute string'";
    return 1;
  }
  permute(argv[1], 0);
  return 0;    
}

解决方案

A stack based non-recursive equivalent of your code:

#include <iostream>
#include <string>

struct State
{
    State (std::string topermute_, int place_, int nextchar_, State* next_ = 0)
        : topermute (topermute_)
        , place (place_)
        , nextchar (nextchar_)
        , next (next_)
    {
    }

    std::string topermute;
    int place;
    int nextchar;

    State* next;
};

std::string swtch (std::string topermute, int x, int y)
{
    std::string newstring = topermute;
    newstring[x] = newstring[y];
    newstring[y] = topermute[x]; //avoids temp variable

    return newstring;
}

void permute (std::string topermute, int place = 0)
{
    // Linked list stack.
    State* top = new State (topermute, place, place);

    while (top != 0)
    {
        State* pop = top;
        top = pop->next;

        if (pop->place == pop->topermute.length () - 1)
        {
            std::cout << pop->topermute << std::endl;
        }

        for (int i = pop->place; i < pop->topermute.length (); ++i)
        {
            top = new State (swtch (pop->topermute, pop->place, i), pop->place + 1, i, top);
        }

        delete pop;
    }
}

int main (int argc, char* argv[])
{
    if (argc!=2)    
    {
        std::cout<<"Proper input is 'permute string'";
        return 1;
    }
    else
    {
        permute (argv[1]);
    }

    return 0;
}

I've tried to make it C-like and avoided c++ STL containers and member functions (used a constructor for simplicity though).

Note, the permutations are generated in reverse order to the original.

I should add that using a stack in this way is just simulating recursion.

这篇关于我如何才能找到一个字符串的所有排列不使用递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！