找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
public class StringPermutation {
// Function to print all the permutations of str
static void printPermutn(String str, String ans) {
// If string is empty
if (str.length() == 0) {
System.out.print(ans + " ");
return;
}
for (int i = 0; i < str.length(); i++) {
// ith character of str
char ch = str.charAt(i);
// Rest of the string after excluding
// the ith character
String ros = str.substring(0, i) + str.substring(i + 1);
// Recurvise call
printPermutn(ros, ans + ch);
}
}
public static void main(String[] args) {
String s = "ABC";
printPermutn(s, "");
}
}
其他回答
其中一个简单的解决方案是使用两个指针继续递归地交换字符。
public static void main(String[] args)
{
String str="abcdefgh";
perm(str);
}
public static void perm(String str)
{ char[] char_arr=str.toCharArray();
helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
if(i==char_arr.length-1)
{
// print the shuffled string
String str="";
for(int j=0; j<char_arr.length; j++)
{
str=str+char_arr[j];
}
System.out.println(str);
}
else
{
for(int j=i; j<char_arr.length; j++)
{
char tmp = char_arr[i];
char_arr[i] = char_arr[j];
char_arr[j] = tmp;
helper(char_arr,i+1);
char tmp1 = char_arr[i];
char_arr[i] = char_arr[j];
char_arr[j] = tmp1;
}
}
}
下面是两个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);
}
}
改进的代码相同
static String permutationStr[];
static int indexStr = 0;
static int factorial (int i) {
if (i == 1)
return 1;
else
return i * factorial(i-1);
}
public static void permutation(String str) {
char strArr[] = str.toLowerCase().toCharArray();
java.util.Arrays.sort(strArr);
int count = 1, dr = 1;
for (int i = 0; i < strArr.length-1; i++){
if ( strArr[i] == strArr[i+1]) {
count++;
} else {
dr *= factorial(count);
count = 1;
}
}
dr *= factorial(count);
count = factorial(strArr.length) / dr;
permutationStr = new String[count];
permutation("", str);
for (String oneStr : permutationStr){
System.out.println(oneStr);
}
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) {
for (int i = 0; i < indexStr; i++){
if(permutationStr[i].equals(prefix))
return;
}
permutationStr[indexStr++] = prefix;
} else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
}
}
}
作为Python生成器,带有现代类型提示:
from typing import Iterator
def permutations(string: str, prefix: str = '') -> Iterator[str]:
if len(string) == 0:
yield prefix
for i, character in enumerate(string):
yield from permutations(string[:i] + string[i + 1:], prefix + character)
for p in permutations('abcd'):
print(p)
递归Python解决方案
def permute(input_str):
_permute("", input_str)
def _permute(prefix, str_to_permute):
if str_to_permute == '':
print(prefix)
else:
for i in range(len(str_to_permute)):
_permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])
if __name__ == '__main__':
permute('foobar')
推荐文章
- 在流中使用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