一 问题描述

商店经理按货物标签的字母顺序对各种货物进行分类，将所有拥有同一字母开头标签的货物存储在同一个仓库中，并用该字母标记。经理收到并登记从商店发出的货物订单，每个订单只需要一种货物，商店经理按照预定的顺序处理请求。请计算经理访问仓库的所有可能方式，以便在一天中一个接一个地解决所有需求。

输入：输入包含一行，其中包含所需货物的所有标签（随机排列）。对每种货物都用标签的起始字母表示，只使用英文字母表的小写字母。订单数量不超过200个。

输出：输出将包含商品经理可以访问其仓库的所有可能订单。对每个仓库都用英文字母表中的一个小写字母表示——货物标签的起始字母。仓库的每个排序在输出文件中只在单独的行上写入一次，并且包含排序的所有行必须按字母顺序排序。任何输出都不会超过2MB字节。

输入样例
bbjd

输出样例

bbdj

bbjd

bdbj

vdjb

bjbd

dbbj

dbbj

djbb

jbbd

jbdb

jdbb

二 算法分析

其实就是按顺序输出字符串的全排列。

三 实现

package collection;

import java.util.*;

public class PermutationDemo<T extends Comparable> {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        List<String> strList = Arrays.asList(str.split(""));
        Collections.sort(strList);
        for (String s : strList) {
            System.out.print(s);
        }
        System.out.println();
        while (new PermutationDemo<String>().next_permutation(strList)) {
            for (String s : strList) {
                System.out.print(s);
            }
            System.out.println();
        }
    }

    public boolean next_permutation(List<T> list) {
        if (list == null || list.size() < 2) {
            return false;
        }
        // 从尾端开始找到第一对相邻元素left和right，满足left < right
        int left = list.size() - 1;
        for (; ; ) {
            int right = left;
            left--;
            if (list.get(left).compareTo(list.get(right)) < 0) {
                // 找到满足条件的这对元素后，从尾端开始往前找到第一个比left大的数，将其与left交换
                int last = list.size() - 1;
                while (list.get(left).compareTo(list.get(last)) >= 0) {
                    last--;
                }
                Collections.swap(list, left, last);
                // 将right之后的所有元素逆序
                Collections.reverse(list.subList(right, list.size()));
                return true;
            }
            // 若找至第一个元素了，把整个list逆序
            if (left == 0) {
                Collections.reverse(list);
                return false;
            }
        }
    }
}

四 测试

绿色为输入，白色为输出。

五 参考

Java实现全排列，基于C++STL的next_permutation - 简书

https://www.jianshu.com/p/3ec9168275f5