Java - Как создать уникальные кортежи объектов (N-измерение)? - PullRequest
Новая
       110

Java - Как создать уникальные кортежи объектов (N-измерение)?

0 голосов
/ 11 августа 2011

У меня есть следующий вызов, мне нужно создать уникальные кортежи объектов из списков объектов. Проблема в том, как я могу это сделать для динамического размера списка (n-размерность)? Это легко, если у вас есть фиксированный размер. Я надеюсь, что кто-то знает сторонний API или подскажет, как мне этого достичь.

В приведенном ниже примере показано 3 списка, поэтому их легче объяснить. У меня есть объекты, отсортированные по классу в списке, например 

lista = {a1,a2}
listb = {b1,b2,b3}
listc = {c1,c2}

Мне бы хотелось иметь следующие кортежи, чтобы каждый объект был спарен один раз с другим: 

tuple1  = {a1,b1,c1}
tuple2  = {a1,b1,c2}
tuple3  = {a1,b2,c1}
tuple4  = {a1,b2,c2}
tuple5  = {a1,b3,c1}
tuple6  = {a1,b3,c2}
tuple7  = {a2,b1,c1}
tuple8  = {a2,b1,c2}
tuple9  = {a2,b2,c1}
tuple10 = {a2,b2,c2}
tuple11 = {a2,b3,c1}
tuple12 = {a2,b3,c2}

Как мне добиться этого в случае
- количество списков динамически
- размер списков динамически

какие-нибудь намеки или идеи? Заранее спасибо

Ответы [ 3 ]

2 голосов
/ 11 августа 2011

Мы можем построить решение следующим образом.Во-первых, обратите внимание, что случай, когда размеры списков варьируются, никогда не является проблемой в современных языках, потому что практически все языки сегодня поддерживают список переменного размера.Более сложным является случай, когда количество списков меняется.

Вот пример Python для фиксированного количества списков: 

lista = ["a1","a2"]
listb = ["b1","b2","b3"]
listc = ["c1","c2"]
[(a,b,c) for a in lista for b in listb for c in listc]

Для Java сделайте то же самое.Вам понадобятся три вложенных цикла for: 

List<String> lista = Arrays.asList("a1","a2");
List<String> listb = Arrays.asList("b1","b2","b3");
List<String> listc = Arrays.asList("c1","c2");

List<List<String>> result = new ArrayList<List<String>>();
for (String a: lista) {
    for (String b: listb) {
        for (String c: listc) {
            result.add(Arrays.asList(a, b, c));
        }
    }
}
System.out.println(result);

Это дает 

[[a1, b1, c1], [a1, b1, c2], [a1, b2, c1], [a1, b2, c2], [a1, b3, c1], [a1, b3, c2], [a2, b1, c1], [a2, b1, c2], [a2, b2, c1], [a2, b2, c2], [a2, b3, c1], [a2, b3, c2]]

Теперь уловка в том, как сделать неопределенное количество циклов for?Одним из способов является использование рекурсии.

Начните с базового варианта 0 списков (или даже 1), а затем спросите себя: как меняется результат, когда я добавляю новый список?Тогда вы можете составить небольшую рекурсивную формулировку.Вам нужна помощь в этом?

(Кроме того: в Python у нас есть itertools для такого рода вещей. Я не знаю ни одного аналога Java, но некоторое прибегание к поиску может кое-что вызвать.)

Хорошо, давайте разработаем рекурсивную формулировку для неограниченного числа списков.Если у вас есть только один список, скажем 

a = ["a1", "a2"]

, то результат будет [["a1"],["a2"]].Но теперь давайте добавим еще один список: 

a = ["b1", "b2"]

Какой сейчас ответ? 

[[a1, b1], [a1, b2], [a2, b1], [a2, b2]]

Как мы это получили?Ответ в том, что мы взяли каждый элемент нового списка и добавили его к каждому элементу в результате.И каждый раз, когда мы добавляем новый список, мы будем делать то же самое.Предположим, теперь мы добавляем ["c1","c2","c3"].Вы видите, что мы получим?Если это так, то теперь вы сможете определить рекурсивный шаг!

ПОЛНЫЙ КОД

Хорошо, я не смог устоять!Вот, пожалуйста. 

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

/**
 * An application requested by a SO user.
 */
public class ProductExample {

    /**
     * Returns a list containing all possible products of a list of lists of strings.
     */
    public static List<List<String>> product(List<List<String>> lists) {
        List<List<String>> result = new ArrayList<List<String>>();

        if (lists.isEmpty()) {
            result.add(new ArrayList<String>());
            return result;
        }

        List<List<String>> partial = product(lists.subList(0, lists.size() - 1));
        for (List<String> list: partial) {
            for (String s: lists.get(lists.size() - 1)) {
                List<String> listCopy = new ArrayList<String>(list);
                listCopy.add(s);
                result.add(listCopy);
            }
        }
        return result;
    }


    public static void main(String[] args) {
        System.out.println(product(
                Arrays.asList(
                        Arrays.asList("a1", "a2"),
                        Arrays.asList("b1", "b2", "b3"),
                        Arrays.asList("c1", "c2"),
                        Arrays.asList("d1", "d2"))));
    }
}

Рэнт: Это намного проще в Python.Или Рубин.:)

1 голос
/ 11 августа 2011

Примерно так должно работать (рассматривается как псевдокод): 

List<List<int>> result = new List<List<int>>();
int[] indices = new int[number_of_lists];
for(int i = 0; i < indices.size(); i++)
  indices[i] = 0;

while(indices[0] < lists[0].size())
{
  List<int> temp = new List<int>();
  for(int i = 0; i < indices.size(); i++)
    temp.add(lists[i].get(indices[i]));
  result.add(temp);

  indices[indices.size() - 1] += 1;
  int i = indices.size();
  while(i >= 1 && indices[i] == lists[i].size())
  {
    indices[i] = 0;
    indices[i-1] += 1;
    i--;
  }
}
0 голосов
/ 11 августа 2011

Наборы Google Guava , кажется, делает что-то похожее на то, что вы хотите , по крайней мере для случая вашего примера.Вам, однако, нужно будет привести полученные списки в формы кортежей.Также это наборы, а не списки, но в вашем примере, по крайней мере, нет повторяющихся записей, так что, возможно, это поможет вам.

...