字符串的排列

题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab、cba。

求整个字符串的排列,可以看成两步

  1. 首先求所有可能出现在第一个位置的字符,即把第一个字符和后面所有的字符交换。下图就是分别把第一个字符a和后面b、c等字符交换的情形。
  2. 第二步固定第一个字符(如图a所示),求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分:后面字符的第一个字符,以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换(如图b所示)。。。

分析到这里,其实可以看出,这就是很典型的递归思路

实现代码如下:

void Permutation(char* pStr)
{
    if(pStr == NULL)
        return;
 
    Permutation(pStr, pStr);
}
 
void Permutation(char* pStr, char* pBegin)
{
    if(*pBegin == '\0')
    {
        printf("%s\n", pStr);
    }
    else
    {
        for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
        {
            char temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
 
            Permutation(pStr, pBegin + 1);
 
            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}

在函数Permutation(char* pStr, char* pBegin)中,指针pStr指向整个字符串的第一个字符,pBegin指向当前我们做排列操作的字符串的第一个字符。在每一次递归的时候,我们从pBegin向后扫描每一个字符(即指针pCh指向的字符)。在交换pBegin和pCh指向的字符之后,我们再对pBegin后面的字符递归地做排列操作,直至pBegin指向字符串的末尾。

测试代码如下:

#include<stdio.h>
 
void Permutation(char* pStr, char* pBegin);
 
void Permutation(char* pStr)
{
    if(pStr == NULL)
        return;
 
    Permutation(pStr, pStr);
}
 
void Permutation(char* pStr, char* pBegin)
{
    if(*pBegin == '\0')
    {
        printf("%s\n", pStr);
    }
    else
    {
        for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
        {
            char temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
 
            Permutation(pStr, pBegin + 1);
 
            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}
 
// ====================测试代码====================
void Test(char* pStr)
{
    if(pStr == NULL)
        printf("Test for NULL begins:\n");
    else
        printf("Test for %s begins:\n", pStr);
 
    Permutation(pStr);
 
    printf("\n");
}
 
int main(int argc, char* argv[])
{
    Test(NULL);
 
    char string1[] = "";
    Test(string1);
 
    char string2[] = "a";
    Test(string2);
 
    char string3[] = "ab";
    Test(string3);
 
    char string4[] = "abc";
    Test(string4);
 
    return 0;
}

扩展1:如果不是求字符的所有排列,而是求字符的所有组合,应该怎么办呢?当输入的字符串中含有相同的字符串时,相同的字符交换位置是不同的排列,但是同一个组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。(字符串的组合

扩展2:输入一个含有8个数字的数组,判断有没有可能把这8个数字分别放到正方体的8个顶点上,使得正方体上三组相对的面上的4个顶点的和相等。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

C++ string类的学习

string类对于处理字符串的一些应用非常的方便,我个人感觉,string和字符数组const char *很像,而且又比字符数组用起来方便的多。 注意其删除,...

46090
来自专栏算法修养

PAT 1040

字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位(P),第4位(A),第6位(T);第二个PAT是第3位(P),第4位(A),第6位(T)...

35570
来自专栏算法修养

CodeForces 666A Reberland Linguistics(DP)

A. Reberland Linguistics time limit per test 1 second memory limit per test ...

42050
来自专栏逆向技术

C语言第十讲,枚举类型简单说明

22830
来自专栏函数式编程语言及工具

Scalaz(13)- Monad:Writer - some kind of logger

  通过前面的几篇讨论我们了解到F[T]就是FP中运算的表达形式(representation of computation)。在这里F[]不仅仅是一种高阶类型...

199100
来自专栏闻道于事

Java之面向对象例子(二)

定义一个Book类,在定义一个JavaBook类继承他 //book类 package com.hanqi.maya.model; public class B...

33180
来自专栏ImportSource

像tomcat容器那样自定义一个 Classloader

最近本人在写一个service container,需要加载指定的jar。需要自定义一个classloader,可以加载到指定的jar包中的class。 以下是...

34290
来自专栏C#

数组未必一定需从0开始,谈一下非0开始的数组

  谈到数组时,当被问及数组是从什么数开始时,估计大部分程序员都会直接说出数组当然是从0开始的。这个回答当然没有错,现在我们就来了解一下C#中的下限非...

20150
来自专栏深度学习与计算机视觉

算法-调整数组顺组使奇数位于偶数前面

题目: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,偶数位于数组的后半部分。 解题思路: 比如我们有一个这样...

22070
来自专栏代码拾遗

反射基础之Array

‘[‘的个数表示的数组的维度,getComponentType()获取的是其组成元素的类型。

14520

扫码关注云+社区

领取腾讯云代金券