组合数学算法（6选2）

Question

在此之后，我现在想编码“6 选择 2”次“4 选择 2”。我的意思是，假设我有 6 个字符“A B C D E F”。第一次选择任意两个字符删除。第二次我想选择 2 个不同的字母进行删除，然后附加这两次试验的结果。因此，我将收到 90（“6 选 2”乘以“4 选 2”）八个字符串。模式中的字符来自相同的模式{1,2,3,4,5,6}。所有字符都是独一无二的，没有重复。

这是我目前的情况。

public String[] genDelPatterns(String design){
    char[] data = design.toCharArray();
    String[] deletionPatterns = new String[15];
    int x = 0;
    StringBuilder sb = new StringBuilder("");
    int index = 0;
    for(int i = 0; i < (6-1); i++){
        for(int j = i+1; j < 6; j++){
            for(int k= 0; k < 6; k++){
                if((k != j) && (k != i))
                    sb.append(String.valueOf(data[k]));
            }
            deletionPatterns[x++] = sb.toString();
            sb = new StringBuilder("");
        }
    }
    return deletionPatterns;
}
public String[] gen8String(String[] pattern1, String[] pattern2){
    String[] combinedPatterns = new String[225];
    int k = 0;
    for(int i = 0; i < 15; i++)
    {
        for(int j = 0; j < 15; j++)
            combinedPatterns[k++] = pattern1[i] + pattern2[j];
    }
    return combinedPatterns;
}

我将这样调用方法：

gen8String(genDelPatterns("143256"), genDelPatterns("254316"));

目前，我正在生成所有可能的 8 字母字符串。但是我只想根据上述规范生成8个字符串。我真的很困惑如何优雅地做这个乘法。我能想到的唯一方法是制作另一种方法“4 选择 2”，然后组合 2 个字符串数组。但这似乎很迂回。

编辑： 8 个字符串的示例类似于“14322516”，考虑到我在调用 gen8String 时已经输入的输入，(143256, 254316）。请注意，前 4 个字符是从 143256 派生的，删除了 5 和 6。但是因为我在第一个路径中删除了 5 和 6，所以我不再被允许在第二个模式中删除相同的东西。因此，我从第二个模式中删除了 3 和 4。

Answer 1

您有一系列方法，每个方法本身都称为变体。为此，我的建议是使用递归方法！要实现您的目标，您必须对这个解决方案有一点经验。

利用递归的方法的简单示例：

public static long factorial(int n) { 
    if (n == 1) return 1; 
    return n * factorial(n-1); 
}

我也可以建议你为方法参数传递对象（构造完美），如果传递简单变量太复杂的话

在我看来，这是该解决方案的核心。

Answer 2

虽然您尝试做的确实有效，但您似乎正在寻找其他方法来实现它。这是我在给定小约束的情况下会做的事情的框架。

// Very pseudo code
// FOR(x,y,z) := for(int x=y; x<z;x++)

string removeCharacter(string s, int banA, int banB){
     string ret = "";
     FOR(i,1,7){
         if(i != banA && i != banB){
              ret += s[i];
         }
     }
    return ret;
}

List<string> Generate(s1,s2){
    List<string> ret = new List<string>();
    FOR(i,1,7) FOR(j,i+1,7) FOR(m,1,7) FOR(n,m+1,7){
         if(m != i && m != j && n != i && n != j){
             string firstHalf  = removeCharacter(s1,i,j);
             string secondHalf = removeCharacter(s2,m,n);
             ret.Add(firstHalf + secondHalf);
         }
    }
    return ret;
}

这应该会生成所有可能的 8 字符字符串。

Answer 3

这是我想出的解决方案。我猜并没有真正采用 "mathematical" 方法。但它完成了工作。

//generating a subset of 90 eight character strings (unique deletion patterns)
    public static String[] gen8String(String[] pattern1, String[] pattern2){
        String[] combinedSubset = new String[90]; //emty array for the subset of 90 strings
        String  combinedString = ""; //string holder for each combined string
        int index = 0; //used for combinedSubset array
        int present = 0; //used to check if all 6 characters are present

        for(int i = 0; i < 15; i++){

            for(int j = 0; j < 15; j++){
                combinedString = pattern1[i] + pattern2[j]; //combine both 4 letter strings into 8 char length string
                char[] parsedString = combinedString.toCharArray(); //parse into array

                //check if all 6 characters are present
                for(int k = 1; k <= 6; k++)
                {
                    if(new String(parsedString).contains(k+"")) {
                        present++;
                    }
                    else
                        break;
                    //if all 6 are present, then add it to combined subset
                    if(present == 6)
                        combinedSubset[index++] = combinedString;
                }
                present = 0;
            }
        }
        return combinedSubset;
    }

组合数学算法（6选2）

Algorithm for combinatorics (6 choose 2)

java

algorithm

math

combinatorics