代码之家 › 专栏 › 技术社区 › MGT

查找单词中非重复字母的所有排列

recursion algorithm java

MGT · 技术社区 · 6 年前

给定3个唯一的字母:可以使用递归函数打印6个字母的可能不重复组合吗?CAT'应输出:CAT、ACT、ATC、TAC、TCA和CTA。这是我的程序,我很难找到递归算法。我的尝试是:

 static void findWords(StringBuilder string, int start, int stride) {
    //1. iterate through all possible combinations of the chars recursively

    System.out.println(string);

    if (stride < string.length() && start < string.length())
    {
        char temp = string.charAt(stride);
        string.setCharAt(stride, string.charAt(start));
        string.setCharAt(start, temp);

        findWords(string, start, stride + 1);

        findWords(string, start + 1, stride + 1 );


    }
}

public static void main(String[] args)
{

   StringBuilder word = new StringBuilder("cat");
   findWords(word,0,1);
}

3 回复 | 直到 6 年前

Coder-Man 6 年前

解决方案:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static List<String> resultList = new ArrayList<>();

    static void computeResult(char[] s, int pos, String resultString) {
        if (pos == 3) {
            resultList.add(resultString);
            return;
        }
        for (int i = 0; i < 3; ++i) {
            if (!resultString.contains(String.valueOf(s[i]))) {
                computeResult(s, pos + 1, resultString + s[i]);
            }
        }
    }

    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();
        computeResult(s, 0, "");
        for(String str : resultList) {
            System.out.println(str);
        }
    }
}

说明:

递归是由 computeResult 功能。它从一个空字符串开始,然后遍历所有可能的字母“c”、“a”和“t”,将它们附加到resultstring中,现在有3个字符串,对于每个字符串,函数 计算机结果 再次调用。然后,它做同样的事情,并且只把那些字母添加到尚未添加的结果字符串中,因此,对于'C',我们附加了'A’,导致“CA”和“T”,导致“CT”,我想剩下的你可以自己弄清楚。

请注意,如果字母是唯一的,则此方法有效。如果不是,例如给了字符串“tat”,则可以将其转换为t1 a1 t2,并对数组[“t1”、“a1”、“t2”执行相同的过程,然后删除这些数字。

javamusings 6 年前

我使用的算法非常简单。将每个字符设置为字符串的第一个字符,并查找与其他两个字符的组合。所以对于字符c,a,t的组合是

c at
c ta

a ct
a tc

t ca
t ac

代码:

static void findWords(String str, int pos) {
    if(str == null || pos < -1) {
        return;
    }

    int len = str.length();
    if(pos + 1 < len) {
        findWords(str, pos + 1);
    }

    //find char swap positions
    int pos1 = (pos + 1) % len;
    int pos2 = (pos - 1 + len) % len;

    char[] chars = str.toCharArray();
    String str1 = new String(new char[] {chars[pos], chars[pos1], chars[pos2]});
    String str2 = new String(new char[] {chars[pos], chars[pos2], chars[pos1]});

    System.out.println(str1);
    System.out.println(str2);
}

public static void main(String[] args) {
    String word = new String("abc");
    findWords(word, 0);
}

geco17 6 年前

这里有一个完整的工作示例,用我的注释来解释算法。

此解决方案基于回溯。了解更多 here 是的。把这个问题看成一棵树。在你的例子中,这个词是“猫”。这里有一些ascii艺术…

                                      cat
                              /        |        \
                            Cat       Act       Tca 
                           /   \     /   \     /   \
                          CAt CTa   ACt ATc   TCa TAc

每次通行证上,你都要写一封信(我把它作为大写字母)。树下越远,你得到的交换就越少,因为你已经固定了一定数量的字母(在0级没有什么是固定的,在1级,一个字母是固定的,这样就可以进行交换;在2级,你就没有更多的交换(交换本身),所以递归达到了它的基本情况。

public static void main(String[] args) {
    // get all the permutations of a word with distinct letters
    Set<String> permutations = getPermutations("cat");

    // print the resulting set
    System.out.println(permutations);
}

private static Set<String> getPermutations(String string) {
    // recursive call to get a permutation of the given string and put it in
    // the set of permutations (initially empty)
    return permute(string, 0, string.length() - 1, new HashSet<String>());
}

private static Set<String> permute(String string, int left, int right, Set<String> set) {
    if (left == right) {
        // swap would be with itself so just add the string
        // this is the base case
        set.add(string);
    } else {
        for (int i = left; i <= right; i++) {
            // indices are different, something can be swapped so swap it
            string = swap(string, left, i);
            // permute the swapped string starting from the next available character
            permute(string, left + 1, right, set);
        }
    }
    return set;
}

// utility method to carry out the swapping
// you could do this with primitive char[] and probably improve performance
// but for the sake of simplicity as it's just an exercise I used a 
// StringBuilder
private static String swap(String in, int i, int j) {
    char tmp1 = in.charAt(i);
    char tmp2 = in.charAt(j);
    StringBuilder sb = new StringBuilder(in);
    // put the char at j in place of the char at i
    sb.setCharAt(i, tmp2);
    // and do the same the other way around
    sb.setCharAt(j, tmp1);

    return sb.toString();
}