找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
倒计时Quickperm算法的通用实现,表示#1(可伸缩,非递归)。
/**
* Generate permutations based on the
* Countdown <a href="http://quickperm.org/">Quickperm algorithm</>.
*/
public static <T> List<List<T>> generatePermutations(List<T> list) {
List<T> in = new ArrayList<>(list);
List<List<T>> out = new ArrayList<>(factorial(list.size()));
int n = list.size();
int[] p = new int[n +1];
for (int i = 0; i < p.length; i ++) {
p[i] = i;
}
int i = 0;
while (i < n) {
p[i]--;
int j = 0;
if (i % 2 != 0) { // odd?
j = p[i];
}
// swap
T iTmp = in.get(i);
in.set(i, in.get(j));
in.set(j, iTmp);
i = 1;
while (p[i] == 0){
p[i] = i;
i++;
}
out.add(new ArrayList<>(in));
}
return out;
}
private static int factorial(int num) {
int count = num;
while (num != 1) {
count *= --num;
}
return count;
}
它需要list,因为泛型不能很好地使用数组。
其他回答
下面是一个简单的Java递归解决方案:
public static ArrayList<String> permutations(String s) {
ArrayList<String> out = new ArrayList<String>();
if (s.length() == 1) {
out.add(s);
return out;
}
char first = s.charAt(0);
String rest = s.substring(1);
for (String permutation : permutations(rest)) {
out.addAll(insertAtAllPositions(first, permutation));
}
return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
ArrayList<String> out = new ArrayList<String>();
for (int i = 0; i <= s.length(); ++i) {
String inserted = s.substring(0, i) + ch + s.substring(i);
out.add(inserted);
}
return out;
}
//插入每个字符到数组列表中
static ArrayList al = new ArrayList();
private static void findPermutation (String str){
for (int k = 0; k < str.length(); k++) {
addOneChar(str.charAt(k));
}
}
//insert one char into ArrayList
private static void addOneChar(char ch){
String lastPerStr;
String tempStr;
ArrayList locAl = new ArrayList();
for (int i = 0; i < al.size(); i ++ ){
lastPerStr = al.get(i).toString();
//System.out.println("lastPerStr: " + lastPerStr);
for (int j = 0; j <= lastPerStr.length(); j++) {
tempStr = lastPerStr.substring(0,j) + ch +
lastPerStr.substring(j, lastPerStr.length());
locAl.add(tempStr);
//System.out.println("tempStr: " + tempStr);
}
}
if(al.isEmpty()){
al.add(ch);
} else {
al.clear();
al = locAl;
}
}
private static void printArrayList(ArrayList al){
for (int i = 0; i < al.size(); i++) {
System.out.print(al.get(i) + " ");
}
}
使用递归的简单python解决方案。
def get_permutations(string):
# base case
if len(string) <= 1:
return set([string])
all_chars_except_last = string[:-1]
last_char = string[-1]
# recursive call: get all possible permutations for all chars except last
permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)
# put the last char in all possible positions for each of the above permutations
permutations = set()
for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
for position in range(len(all_chars_except_last) + 1):
permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:]
permutations.add(permutation)
return permutations
另一种简单的方法是遍历字符串,选择尚未使用的字符并将其放入缓冲区,继续循环,直到缓冲区大小等于字符串长度。我更喜欢这个回溯跟踪解决方案,因为:
容易理解 容易避免重复 输出是排序的
下面是java代码:
List<String> permute(String str) {
if (str == null) {
return null;
}
char[] chars = str.toCharArray();
boolean[] used = new boolean[chars.length];
List<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
Arrays.sort(chars);
helper(chars, used, sb, res);
return res;
}
void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
if (sb.length() == chars.length) {
res.add(sb.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
// avoid duplicates
if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
continue;
}
// pick the character that has not used yet
if (!used[i]) {
used[i] = true;
sb.append(chars[i]);
helper(chars, used, sb, res);
// back tracking
sb.deleteCharAt(sb.length() - 1);
used[i] = false;
}
}
}
str输入:1231
输出列表:{1123,1132,1213,1231,1312,1321,2113,2131,2311,3112,3121,3211}
注意,输出是排序的,没有重复的结果。
下面是两个c#版本(仅供参考): 1. 打印所有排列 2. 返回所有排列
算法的基本要点是(可能下面的代码更直观-尽管如此,下面的代码是做什么的一些解释): -从当前索引到集合的其余部分,交换当前索引处的元素 -递归地获得下一个索引中剩余元素的排列 -恢复秩序,通过重新交换
注意:上述递归函数将从起始索引中调用。
private void PrintAllPermutations(int[] a, int index, ref int count)
{
if (index == (a.Length - 1))
{
count++;
var s = string.Format("{0}: {1}", count, string.Join(",", a));
Debug.WriteLine(s);
}
for (int i = index; i < a.Length; i++)
{
Utilities.swap(ref a[i], ref a[index]);
this.PrintAllPermutations(a, index + 1, ref count);
Utilities.swap(ref a[i], ref a[index]);
}
}
private int PrintAllPermutations(int[] a)
{
a.ThrowIfNull("a");
int count = 0;
this.PrintAllPermutations(a, index:0, count: ref count);
return count;
}
版本2(与上面相同-但返回排列而不是打印)
private int[][] GetAllPermutations(int[] a, int index)
{
List<int[]> permutations = new List<int[]>();
if (index == (a.Length - 1))
{
permutations.Add(a.ToArray());
}
for (int i = index; i < a.Length; i++)
{
Utilities.swap(ref a[i], ref a[index]);
var r = this.GetAllPermutations(a, index + 1);
permutations.AddRange(r);
Utilities.swap(ref a[i], ref a[index]);
}
return permutations.ToArray();
}
private int[][] GetAllPermutations(int[] p)
{
p.ThrowIfNull("p");
return this.GetAllPermutations(p, 0);
}
单元测试
[TestMethod]
public void PermutationsTests()
{
List<int> input = new List<int>();
int[] output = { 0, 1, 2, 6, 24, 120 };
for (int i = 0; i <= 5; i++)
{
if (i != 0)
{
input.Add(i);
}
Debug.WriteLine("================PrintAllPermutations===================");
int count = this.PrintAllPermutations(input.ToArray());
Assert.IsTrue(count == output[i]);
Debug.WriteLine("=====================GetAllPermutations=================");
var r = this.GetAllPermutations(input.ToArray());
Assert.IsTrue(count == r.Length);
for (int j = 1; j <= r.Length;j++ )
{
string s = string.Format("{0}: {1}", j,
string.Join(",", r[j - 1]));
Debug.WriteLine(s);
}
Debug.WriteLine("No.OfElements: {0}, TotalPerms: {1}", i, count);
}
}
推荐文章
- 在流中使用Java 8 foreach循环移动到下一项
- 访问限制:'Application'类型不是API(必需库rt.jar的限制)
- 用Java计算两个日期之间的天数
- 如何配置slf4j-simple
- 在Jar文件中运行类
- 带参数的可运行?
- 我如何得到一个字符串的前n个字符而不检查大小或出界?
- 我可以在Java中设置enum起始值吗?
- Java中的回调函数
- c#和Java中的泛型有什么不同?和模板在c++ ?
- 在Java中,流相对于循环的优势是什么?
- Jersey在未找到InjectionManagerFactory时停止工作
- 在Java流是peek真的只是调试?
- Recyclerview不调用onCreateViewHolder
- 将JSON字符串转换为HashMap