找出弦的所有排列的优雅方法是什么。例如,ba的排列,将是ba和ab,但更长的字符串,如abcdefgh?是否有Java实现示例?
当前回答
//循环'整个字符数组,并保持'i'作为你的排列的基础,并像你交换[ab, ba]一样继续寻找组合
public class Permutation {
//Act as a queue
private List<Character> list;
//To remove the duplicates
private Set<String> set = new HashSet<String>();
public Permutation(String s) {
list = new LinkedList<Character>();
int len = s.length();
for(int i = 0; i < len; i++) {
list.add(s.charAt(i));
}
}
public List<String> getStack(Character c, List<Character> list) {
LinkedList<String> stack = new LinkedList<String>();
stack.add(""+c);
for(Character ch: list) {
stack.add(""+ch);
}
return stack;
}
public String printCombination(String s1, String s2) {
//S1 will be a single character
StringBuilder sb = new StringBuilder();
String[] strArr = s2.split(",");
for(String s: strArr) {
sb.append(s).append(s1);
sb.append(",");
}
for(String s: strArr) {
sb.append(s1).append(s);
sb.append(",");
}
return sb.toString();
}
public void printPerumtation() {
int cnt = list.size();
for(int i = 0; i < cnt; i++) {
Character c = list.get(0);
list.remove(0);
List<String> stack = getStack(c, list);
while(stack.size() > 1) {
//Remove the top two elements
String s2 = stack.remove(stack.size() - 1);
String s1 = stack.remove(stack.size() - 1);
String comS = printCombination(s1, s2);
stack.add(comS);
}
String[] perms = (stack.remove(0)).split(",");
for(String perm: perms) {
set.add(perm);
}
list.add(c);
}
for(String s: set) {
System.out.println(s);
}
}
}
其他回答
我的实现基于Mark Byers上面的描述:
static Set<String> permutations(String str){
if (str.isEmpty()){
return Collections.singleton(str);
}else{
Set <String> set = new HashSet<>();
for (int i=0; i<str.length(); i++)
for (String s : permutations(str.substring(0, i) + str.substring(i+1)))
set.add(str.charAt(i) + s);
return set;
}
}
基于Mark Byers的回答,我想出了这个解决方案:
JAVA
public class Main {
public static void main(String[] args) {
myPerm("ABCD", 0);
}
private static void myPerm(String str, int index)
{
if (index == str.length()) System.out.println(str);
for (int i = index; i < str.length(); i++)
{
char prefix = str.charAt(i);
String suffix = str.substring(0,i) + str.substring(i+1);
myPerm(prefix + suffix, index + 1);
}
}
}
C#
我还使用新的c# 8.0范围操作符在c#中编写了该函数
class Program
{
static void Main(string[] args)
{
myPerm("ABCD", 0);
}
private static void myPerm(string str, int index)
{
if (index == str.Length) Console.WriteLine(str);
for (int i = index; i < str.Length; i++)
{
char prefix = str[i];
string suffix = str[0..i] + str[(i + 1)..];
myPerm(prefix + suffix, index + 1);
}
}
我们只是把每个字母放在开头,然后排列。 第一次迭代是这样的:
/*
myPerm("ABCD",0)
prefix = "A"
suffix = "BCD"
myPerm("ABCD",1)
prefix = "B"
suffix = "ACD"
myPerm("BACD",2)
prefix = "C"
suffix = "BAD"
myPerm("CBAD",3)
prefix = "D"
suffix = "CBA"
myPerm("DCBA",4)
Console.WriteLine("DCBA")
*/
所有之前的贡献者都很好地解释和提供了代码。我想我也应该分享这个方法,因为它可能也会帮助到别人。解决方案基于(堆算法)
一些事情:
注意excel中最后一项的描述只是为了帮助你更好地可视化逻辑。因此,最后一列的实际值将是2,1,0(如果我们要运行代码,因为我们处理的是数组,而数组以0开头)。 交换算法基于当前位置的偶数或奇数值发生。如果你看一下swap方法被调用的位置,你就会明白这一点。你可以看到发生了什么。
事情是这样的:
public static void main(String[] args) {
String ourword = "abc";
String[] ourArray = ourword.split("");
permute(ourArray, ourArray.length);
}
private static void swap(String[] ourarray, int right, int left) {
String temp = ourarray[right];
ourarray[right] = ourarray[left];
ourarray[left] = temp;
}
public static void permute(String[] ourArray, int currentPosition) {
if (currentPosition == 1) {
System.out.println(Arrays.toString(ourArray));
} else {
for (int i = 0; i < currentPosition; i++) {
// subtract one from the last position (here is where you are
// selecting the the next last item
permute(ourArray, currentPosition - 1);
// if it's odd position
if (currentPosition % 2 == 1) {
swap(ourArray, 0, currentPosition - 1);
} else {
swap(ourArray, i, currentPosition - 1);
}
}
}
}
这对我很有效。
import java.util.Arrays;
public class StringPermutations{
public static void main(String args[]) {
String inputString = "ABC";
permute(inputString.toCharArray(), 0, inputString.length()-1);
}
public static void permute(char[] ary, int startIndex, int endIndex) {
if(startIndex == endIndex){
System.out.println(String.valueOf(ary));
}else{
for(int i=startIndex;i<=endIndex;i++) {
swap(ary, startIndex, i );
permute(ary, startIndex+1, endIndex);
swap(ary, startIndex, i );
}
}
}
public static void swap(char[] ary, int x, int y) {
char temp = ary[x];
ary[x] = ary[y];
ary[y] = temp;
}
}
这就是我通过对排列和递归函数调用的基本理解所做的。虽然要花点时间,但都是独立完成的。
public class LexicographicPermutations {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="abc";
List<String>combinations=new ArrayList<String>();
combinations=permutations(s);
Collections.sort(combinations);
System.out.println(combinations);
}
private static List<String> permutations(String s) {
// TODO Auto-generated method stub
List<String>combinations=new ArrayList<String>();
if(s.length()==1){
combinations.add(s);
}
else{
for(int i=0;i<s.length();i++){
List<String>temp=permutations(s.substring(0, i)+s.substring(i+1));
for (String string : temp) {
combinations.add(s.charAt(i)+string);
}
}
}
return combinations;
}}
生成输出为[abc, acb, bac, bca, cab, cba]。
它背后的基本逻辑是
对于每个字符,将其视为第一个字符,并找出剩余字符的组合。例[abc](abc的组合)->。
a->[bc](a x Combination of (bc))->{abc,acb} b->[ac](b x组合(ac))->{bac,bca} c->[ab](c x Combination of (ab))->{cab,cba}
然后递归地分别调用每个[bc],[ac]和[ab]。
推荐文章
- 在流中使用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