关于使用递归的置换的问题 [英] Question on permutation using recursion

问题描述

预期输出：abc - > abc，acb，bca，bac，cab，cba

示例输出：当传递字符串s =abc时我得到：cc ccc ccc





（越野车）代码是：

 #include< stdio.h> 
 #include< cs50.h> 
 #include< stdlib.h> 
 #include< string.h> 
 
 
 string subS（string fullS，int s，int len）; 
 string permut（string s，int n）; 
 void swap（string s，int a，int b）; 
 
 int main（int argc，string argv []）
 {
 
 if（argc！= 2）
 printf（usage：./置换5）; 
 
 int n = strlen（argv [1]）; 
 permut（argv [1]，n）; 
 
 //打印字符串s的排列，长度为n 
 
 
} 
 string subS（string fullS，int s，int len）
 
 {
 string sub = fullS; 
 
 for（int j = 0; j< len; j ++）
 {
 sub [j] = fullS [s]; 
 s = s + 1; 
} 
 sub [len] ='\0'; 
返回子; 
} 
 
 
 string permut（string s，int n）
 {
 if（s！= NULL）
 {
 
 
 if（n == 1）
 return s; 
 else 
 {
 string dummy_s = s; //虚拟变量，以便不传递字符串
 
 
 string sub = subS（dummy_s，1 ，n-1）; //得到s的子串，从s [1]开始，长度为n-1 
 
 string smaller = permut（sub，n-1）; //置换子串
 
 string final = strncat（small，s，1）; //将s的第一个字母附加到置换字符串。将使用它来打印
 
 
 
 $ b //的排列通过取s [0]生成排列将它附加到较小。这是使用字符串final完成并用其左边的neigbour交换s [0]并打印这些字符串中的每一个
 for（int i = n-1; i> 0; i--）
 {
 printf（％s \ n，final）; 
 swap（final，i，i-1）; 
} 
 
} 
} 
返回s; 
 
} 
 
 void swap（string s，int a，int b）
 {
 if（a< = b）
 return ; 
 else 
 {
 char c = s [a]; 
 s [a] = s [b]; 
 s [b] = c; 
 
} 
} 

我的尝试：



试图通过评论提供我的代码逻辑。不知道我应该在这里添加什么。

解决方案

在我看来，你的代码过于复杂。



您可以使用原始字符串进行工作：置换函数可以迭代（接收到的子字符串）字符，在每次迭代（比如n ^th ）中用第一个字符交换n ^th 字符

，然后在结果上调用自身递归（更小） ）substring并最终通过再次交换来恢复收到的内容。

据我所知，你的代码是完全错误的。

首先你需要研究算法直到你理解它为止。

拿一张纸和练习，认为你获得所有排列的唯一工具是交换功能，想想机械。建议：练习至少4个字母以暴露重复的模式。

递归排列 - C ++论坛 [ ^ ]



学习一种或多种分析方法可能会凝聚， EW Djikstra自上而下的方法是一个良好的开端。

https：// en.wikipedia.org/wiki/Top-down_and_bottom-up_design [ ^ ]

https://en.wikipedia.org/wiki/Structured_programming [ ^ ]

https://en.wikipedia.org/wiki/Edsger_W._Dijkstra [ ^ ]

https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF [ ^

expected output: "abc" --> abc,acb,bca,bac,cab,cba
example outputs: when passed string s="abc" i get: cc ccc ccc


the (buggy) code is:

#include <stdio.h>
#include <cs50.h>
#include <stdlib.h>
#include <string.h>


string subS(string fullS, int s,int len);
string permut(string s ,int n);
void swap(string s,int a,int b);

int main (int argc, string argv[])
{

    if (argc!=2)
    printf("usage: ./permutation 5");

    int n = strlen(argv[1]);
    permut(argv[1],n);

    // print permutations of string s , of length n


}
  string subS(string fullS, int s,int len)

   {
      string sub = fullS;

       for(int j=0;j<len;j++)
       {
           sub[j]=fullS[s];
           s=s+1;
       }
        sub[len]='\0';
       return sub;
   }


    string permut(string s ,int n)
    {
        if (s!=NULL)
        {


            if(n==1)
                return s;
            else
            {
                string dummy_s=s;// dummy variable so as not to pass the string
                

                string sub=subS(dummy_s,1,n-1);// get the substring of s starting at s[1] and of length n-1
                
                string smaller=permut(sub,n-1);// permute the substring
                
                string final = strncat(smaller,s,1); // append the first letter of s to the permuted string.will be using it to print the permutations of
                 
                

//generating the permutations by taking s[0] and appending it to "smaller".This is done using a string "final" and swapping s[0] with its left neigbour and printing the each of these strings 
                for (int i=n-1;i>0;i--)
                {
                    printf("%s\n",final);
                    swap(final,i,i-1);
                }
                
            }
        }
        return s;

    }

    void swap(string s,int a,int b)
    {
        if (a<=b)
            return;
        else
        {
            char c= s[a];
            s[a]=s[b];
            s[b]=c;

        }
    }

What I have tried:

have tried to provide the logic of my code throug comments.Not sure what i should add here.

解决方案

It looks to me you are overcomplicating the code.

You maight work always with the original string: the permutation function could iterate over (the received substring) characters, at each iteration (say n^th) swapping the n^th character
with the first one, then calling itself recursive on the resulting (smaller) substring and eventually restoring the received content by swapping again.

As far as I understand it, your code is completely wrong.
First of all you need to study the algorithm until you understand it.
Take a sheet of paper and practice, think that your only tool to get all permutation is the swap function, think mechanical. Advice: Practice with at least 4 letters to expose repetitive patterns.
Recursion permutations - C++ Forum[^]

It may gelp to learn one or more analyze methods, E.W. Djikstra top-Down method is a good start.
https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design[^]
https://en.wikipedia.org/wiki/Structured_programming[^]
https://en.wikipedia.org/wiki/Edsger_W._Dijkstra[^]
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF[^]

这篇关于关于使用递归的置换的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！