Получить все возможные комбинации двух массивов строк - PullRequest
Новая
       5

Получить все возможные комбинации двух массивов строк

0 голосов
/ 14 ноября 2018

У меня есть массив из двух строк: 

A("0", "1", "2", "3", "4", "5", "6", "7")
B("a", "b", "c", "d", "e")

Перестановка для определения количества возможных комбинаций: 

[((8!)/(8-5)!)*((3!)/(3-2)!)]*[(7!)/((2!)*(7-2)!)]
40320 * 21 = 846720

Как получить все комбинации между двумя массивами, используя5 элементов A и 2 элемента B, без повторений?

Для этого я сделал код для извлечения всех «комбинационных клавиш»: 

package wodlist;

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

public class GenerateKey {

 static void perm1(String c0, int n0, String c1, int n1, String s, 
 List<String> result) {
    if (n0 < 0 || n1 < 0)
        return;
    else if (n0 == 0 && n1 == 0)
        result.add(s);
    else {
        perm1(c0, n0 - 1, c1, n1, s + c0, result);
        perm1(c0, n0, c1, n1 - 1, s + c1, result);
    }

  }

  static List<String> perm(String c0, int n0, String c1, int n1) {
    List<String> result = new ArrayList<>();
    perm1(c0, n0, c1, n1, "", result);
    return result;
  }
}

При вызове функции perm("A", 5, "B", 2) У меня будет результат, подобный следующему: 

[AAAAABB, AAAABAB, AAAABBA, AAABAAB, AAABABA, AAABBAA, AABAAAB, AABAABA, AABABAA, AABBAAA, ABAAAAB, ABAAABA, ABAABAA, ABABAAA, ABBAAAA, BAAAAAB, BAAAABA, BAAABAA, BAABAAA, BABAAAA, BBAAAAA]

Это «ключ», но как я могу получить все комбинации каждого ключа, используя 5 элементов A и 2 элемента B?

Например: 

AAAAABB = {0,2,3,4,5,a,b}, {0,2,3,4,5,a,c}, {0,2,3,4,5,a,d}...
AAAABAB = ...

Я сделал этот пример, который имеет ту же «логику», но я не могу с ней повторить, так как в нем я знал количество возможных комбинаций.Там, где у меня есть оба массива, количество символов, которые я буду использовать каждый, но проблема этого с другим состоит в том, что я знаю количество возможных комбинаций каждой «клавиши».Что-то, чего я не знаю о проблеме, описанной выше. 

    String[] A = new String[]{"1","2","3"};
    String[] B = new String[]{"a","b","c"};
    //key
    String[] AAB = new String[18];
    String[] ABA = new String[18];
    String[] BAA = new String[18];
    //result
    String[] S = new String[54];
    //
    //[A0,A1,B]
    int aabIndex = 0, abaIndex = 0, baaIndex=0;
    for (int a0Index = 0; a0Index < 3; a0Index++){
        for (int a1Index = 0; a1Index < 3; a1Index++) {
            // skip when A0 == A1
            if (a0Index == a1Index) continue;
            // scroll through b
            for(int bIndex = 0; bIndex < 3; bIndex++){
                AAB[aabIndex++] = A[a0Index] + A[a1Index] + B[bIndex];
                ABA[abaIndex++] = A[a0Index] + B[bIndex] + A[a1Index];
                BAA[baaIndex++] = B[bIndex] + A[a0Index] + A[a1Index];
            }
        }
    }

Перестановка для получения вышеуказанного результата: 

[Arrangement(3,2)*Arrangement(3,1)]*Combination(3,2)
[(3!/(3-2)!)*(3!/(3-1)!]*[3!/(2!*(3-2)!) = 
[6 * 3] * 3 = 54

Кто-нибудь может мне помочь?

1 Ответ

0 голосов
/ 15 ноября 2018

Попробуйте это: 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import static java.util.stream.Collectors.toList;

public class Perm2 {

  public static void main(String[] args) {
    List<String> listA = Arrays.asList("1", "2", "3");
    List<String> listB = Arrays.asList("a", "b", "c");

    List<String> result = perm2(listA, 2, listB, 1);
    result.forEach(System.out::println);
    System.out.println("--- count = " + result.size());
  }

  private static List<String> perm2(List<String> listA, int numA, List<String> listB, int numB) {
    if (numA == 0 && numB == 0) return Collections.singletonList("");

    List<String> forSelect = new ArrayList<>();
    if (numA > 0) forSelect.addAll(listA);
    if (numB > 0) forSelect.addAll(listB);

    List<String> result = new ArrayList<>();
    for (String elem : forSelect) {
      List<String> newListA = without(listA, elem);
      int newNumA = numA - (listA.contains(elem) ? 1 : 0);
      List<String> newListB = without(listB, elem);
      int newNumB = numB - (listB.contains(elem) ? 1 : 0);
      result.addAll(
            perm2(newListA, newNumA, newListB, newNumB).stream()
                  .map(s -> elem + s)
                  .collect(toList()));
    }
    return result;
  }

  private static List<String> without(List<String> list, String elem) {
    return list.stream().filter(e -> e != elem).collect(toList());
  }

}

Я предполагаю, что все элементы из listA и listB различны и что количество элементов для выбора находится в диапазоне 0..length.

...