Проверьте все возможные комбинации строк

Question

Проблема в следующем.Есть несколько строк, которые имеют неуникальные идентификаторы:

id value
0: {1,2,3}
0: {1,2,2}

1: {1,2,3}

2: {1,2,3}
2: {1,1,3}

У меня есть функция equals, которая может сравнивать несколько строк друг с другом.Мне нужно написать код, который выбирает строки в качестве ввода функции equals.Выбранные строки должны иметь уникальные идентификаторы, НО я должен проверить все возможные комбинации уникальных идентификаторов.Например, если есть 5 строк с идентификаторами: 0,0,1,2,3, то я должен проверить следующие две комбинации идентификаторов: 0,1,2,3 и 0,1,2,3, потому что 0появляется дважды.Разумеется, каждая из этих двух комбинаций будет состоять из уникальных строк с id = 0.

Мой фрагмент кода следующий:

public class Test {
public static void main(String[] args) {
  ArrayList<Row> allRows = new ArrayList<Row>();
  allRows.add(new Row(0,new int[]{1,2,3}));
  allRows.add(new Row(0,new int[]{1,2,2}));
  allRows.add(new Row(1,new int[]{1,2,3}));
  allRows.add(new Row(2,new int[]{1,2,3}));
  allRows.add(new Row(2,new int[]{1,1,3}));

  boolean answer = hasEqualUniqueRows(allRows);
}

private boolean hasEqualUniqueRows(ArrayList<Row> allTokens) {
    for (int i=0; i<allTokens.size(); i++) {
        ArrayList<Integer[]> rows = new ArrayList<Integer[]>();
        rows = findUniqueRows(i,allTokens);
        boolean answer = equalsExceptForNulls(rows);
        if (answer) return true;
    }
    return false;
}
// Compare rows for similarities
public static <T> boolean equalsExceptForNulls(ArrayList<T[]> ts) {
    for (int i=0; i<ts.size(); i++) {
        for (int j=0; j<ts.size(); j++) {
            if (i != j) {
                boolean answer = equals(ts.get(i),ts.get(j));
                if (!answer) return false;
            }
        }
    }
    return true;
}

public static <T> boolean equals(T[] ts1, T[] ts2) {
    if (ts1.length != ts2.length) return false;
    for(int i = 0; i < ts1.length; i++) {
       T t1 = ts1[i], t2 = ts2[i];
       if (t1 != null && t2 != null && !t1.equals(t2)) 
           return false;
    }
    return true;
}

class Row {
          private String key;
          private Integer[] values;

      public Row(String k,Integer[] v) {
          this.key = k;
          this.values = v;
      }

      public String getKey() {
          return this.key;
      }

      public Integer[] getValues() {
          return this.values;
      }
}

}

Поскольку число строк с уникальными идентификаторами априори неизвестно, я не знаю, как решить эту проблемупроблема.Какие-либо предложения?Спасибо.

Редактировать # 1 Я обновил код.Теперь это более полно.Но в ней отсутствует реализация функции findUniqueRows.Эта функция должна выбирать строки из ArrayList, которые имеют уникальные ключи (идентификаторы).Может ли кто-нибудь помочь мне развить эту функцию?Спасибо.

Answer 1

Предполагая, что цель состоит в том, чтобы найти каждую комбинацию без дубликатов, вы можете сделать это следующим образом. Тест для поиска дубликатов - это просто подтверждение того, что он не генерирует дубликаты.

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    public static void main(String... args) {
        Bag<Integer> b = new Bag<>();
        b.countFor(1, 2);
        b.countFor(2, 1);
        b.countFor(3, 3);
        Set<String> set = new LinkedHashSet<>();
        for (List<Integer> list : b.combinations()) {
            System.out.println(list);
            String s = list.toString();
            if (!set.add(s))
                System.err.println("Duplicate entry " + s);
        }
    }
}

class Bag<E> {
    final Map<E, AtomicInteger> countMap = new LinkedHashMap<>();

    void countFor(E e, int n) {
        countMap.put(e, new AtomicInteger(n));
    }

    void decrement(E e) {
        AtomicInteger ai = countMap.get(e);
        if (ai.decrementAndGet() < 1)
            countMap.remove(e);
    }

    void increment(E e) {
        AtomicInteger ai = countMap.get(e);
        if (ai == null)
            countMap.put(e, new AtomicInteger(1));
        else
            ai.incrementAndGet();
    }

    List<List<E>> combinations() {
        List<List<E>> ret = new ArrayList<>();
        List<E> current = new ArrayList<>();
        combinations0(ret, current);
        return ret;
    }

    private void combinations0(List<List<E>> ret, List<E> current) {
        if (countMap.isEmpty()) {
            ret.add(new ArrayList<E>(current));
            return;
        }
        int position = current.size();
        current.add(null);
        List<E> es = new ArrayList<>(countMap.keySet());
        if (es.get(0) instanceof Comparable)
            Collections.sort((List) es);
        for (E e : es) {
            current.set(position, e);
            decrement(e);
            combinations0(ret, current);
            increment(e);
        }
        current.remove(position);
    }
}