Algorithm 版 (精华区)

发信人: sino (茶水︿△︿万艳同杯), 信区: Algorithm
标  题: ACM竞赛辅导--2.1.0
发信站: 哈工大紫丁香 (2000年11月08日20:28:25 星期三), 站内信件

题目：
        键盘输入一个仅由小写字母组成的字符串，输出该串中任取M个字母的所有排列
        及排列总数。
思路：
        观察对于输入caabab的输出结果：
        aaa aab aac aba abb abc aca acb baa bab
        bac bba bbc bca bcb bcc caa cab cbb
        按字母顺序，此序列为递增序列。
        也就是说，我们可用像排字然数类似的方法来排列这些字母。
        首先，将原字符串排序。排序对此题要求的结果没有影响，却可方便我们编程。
        再初始化输出排列，使其为排列中的最小值，在上例中为aaa。
        然后就像自然数加一的操作，每次取下一个与上次不同的排列。
要点：
        使用布尔型数组used记录字母使用的状态（称作标志数组）。
        “每次取下一个与上次不同的排列”时如何找下一个不同的字母呢？
        用比较死板的方法，顺着排序过的字符串前进，总可以找到下一个不同的字母。
        （排序工作没有白费）
        如果基于效率考虑，可以将字符串中出现新字母的位置都记录下来。
测试数据：（只给出总数）
        输入字符串      M       输出结果
        abcdef          6         720
        abcdefghijk     4         7920
        adaade          3         19
        ashjysssjjy     4         387
        adadadererer    5         960
总结： 这是一道基本题。题目不难，但可钻的地方很多。

--
撷取生活中每一朵清新的浪花,智慧的浪花..汇成音乐的海洋.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.226.245]