找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
基于Heap算法的我的实现:
import java.util.ArrayList;
import java.util.List;
public class PermutationString {
public static List<String> permute(char[] str, int n) {
List<String> permutations = new ArrayList<>();
if (n == 1) {
permutations.add(new String(str));
}
else {
for (int i = 0; i < n; i++) {
permutations.addAll(permute(str, n-1));
if (n % 2 == 0) {
swap(str, i, n-1);
}
else {
swap(str, 0, n-1);
}
}
}
return permutations;
}
public static void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
public static void main(String[] args) {
List<String> permutations = permute("abcdefgh".toCharArray(), 8);
System.out.println(permutations);
}
}
时间复杂度为O(n!* n), O(n)为空间复杂度。
其他回答
在这里和其他论坛给出的所有解决方案中,我最喜欢Mark Byers。这个描述实际上让我自己思考并编写了代码。 可惜我不能投票支持他的解决方案,因为我是新手。 无论如何,这是我对他的描述的实现
public class PermTest {
public static void main(String[] args) throws Exception {
String str = "abcdef";
StringBuffer strBuf = new StringBuffer(str);
doPerm(strBuf,0);
}
private static void doPerm(StringBuffer str, int index){
if(index == str.length())
System.out.println(str);
else { //recursively solve this by placing all other chars at current first pos
doPerm(str, index+1);
for (int i = index+1; i < str.length(); i++) {//start swapping all other chars with current first char
swap(str,index, i);
doPerm(str, index+1);
swap(str,i, index);//restore back my string buffer
}
}
}
private static void swap(StringBuffer str, int pos1, int pos2){
char t1 = str.charAt(pos1);
str.setCharAt(pos1, str.charAt(pos2));
str.setCharAt(pos2, t1);
}
}
我更喜欢这个解决方案,而不是第一个解决方案,因为这个解决方案使用StringBuffer。我不会说我的解决方案没有创建任何临时字符串(它实际上在system.out.println中创建,其中调用StringBuffer的toString())。但我只是觉得这比第一个解决方案好太多的字符串字面值被创建。可能有些性能人员可以根据“内存”来评估这一点(对于“时间”来说,由于额外的“交换”,它已经滞后了)
我们可以用阶乘来计算有多少字符串以某个字母开头。
示例:取输入abcd。(3!) == 6个字符串将以abcd中的每个字母开头。
static public int facts(int x){
int sum = 1;
for (int i = 1; i < x; i++) {
sum *= (i+1);
}
return sum;
}
public static void permutation(String str) {
char[] str2 = str.toCharArray();
int n = str2.length;
int permutation = 0;
if (n == 1) {
System.out.println(str2[0]);
} else if (n == 2) {
System.out.println(str2[0] + "" + str2[1]);
System.out.println(str2[1] + "" + str2[0]);
} else {
for (int i = 0; i < n; i++) {
if (true) {
char[] str3 = str.toCharArray();
char temp = str3[i];
str3[i] = str3[0];
str3[0] = temp;
str2 = str3;
}
for (int j = 1, count = 0; count < facts(n-1); j++, count++) {
if (j != n-1) {
char temp1 = str2[j+1];
str2[j+1] = str2[j];
str2[j] = temp1;
} else {
char temp1 = str2[n-1];
str2[n-1] = str2[1];
str2[1] = temp1;
j = 1;
} // end of else block
permutation++;
System.out.print("permutation " + permutation + " is -> ");
for (int k = 0; k < n; k++) {
System.out.print(str2[k]);
} // end of loop k
System.out.println();
} // end of loop j
} // end of loop i
}
}
下面是两个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);
}
}
使用位操作可以很容易地做到这一点。“我们都知道,任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1,因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)
private void getPermutation(String str)
{
if(str==null)
return;
Set<String> StrList = new HashSet<String>();
StringBuilder strB= new StringBuilder();
for(int i = 0;i < (1 << str.length()); ++i)
{
strB.setLength(0); //clear the StringBuilder
for(int j = 0;j < str.length() ;++j){
if((i & (1 << j))>0){ // to check whether jth bit is set
strB.append(str.charAt(j));
}
}
if(!strB.toString().isEmpty())
StrList.add(strB.toString());
}
System.out.println(Arrays.toString(StrList.toArray()));
}
为排列和组合添加更详细的NcK/NcR
public static void combinationNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}
public static void permNcK(List<String> inputList, int chooseCount, List<String> resultList) {
for (int count = 0; count < inputList.size(); count++) {
permNcK(inputList, "", chooseCount, resultList);
resultList = new ArrayList<String>();
Collections.rotate(inputList, 1);
System.out.println("-------------------------");
}
}
public static void permNcK(List<String> inputList, String prefix, int chooseCount, List<String> resultList) {
if (chooseCount == 0)
resultList.add(prefix);
else {
for (int i = 0; i < inputList.size(); i++)
combinationNcK(inputList.subList(i + 1, inputList.size()), prefix + "," + inputList.get(i), chooseCount - 1, resultList);
// Finally print once all combinations are done
if (prefix.equalsIgnoreCase("")) {
resultList.stream().map(str -> str.substring(1)).forEach(System.out::println);
}
}
}
public static void main(String[] args) {
List<String> positions = Arrays.asList(new String[] { "1", "2", "3", "4", "5", "6", "7", "8" });
List<String> resultList = new ArrayList<String>();
//combinationNcK(positions, "", 3, resultList);
permNcK(positions, 3, resultList);
}
推荐文章
- 在流中使用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