Блог

Мне трудно разобраться в следующей ситуации. Лучшим способом объяснить может быть пример

У меня есть объект Map<Column,Set<Row>> . Допустим, он содержит следующие данные:

 ColumnA['abc','def']
ColumnB['efg','hij','klm']
ColumnC['nop']
ColumnD['qrs','tuv','wxy','zzz']
  

Я пытаюсь сгенерировать следующий результат:

 Row1[abc,efg,nop,qrs]
Row2[abc,efg,nop,tuv]
Row3[abc,efg,nop,wxy]
Row4[abc,efg,nop,zzz]
Row5[abc,hij,nop,qrs]
Row6[abc,hij,nop,wxy]
etc...
  

Таким образом, в этом случае всего будет 24 строки.

Однако количество столбцов и строк являются динамическими. Я чувствую, что это нужно как-то рекурсивно сделать, но я не уверен, с чего начать.

Любая помощь будет оценена.

Обновление — я создал древовидную структуру, которая, похоже, работает.

     DefaultMutableTreeNode root = new DefaultMutableTreeNode();
    Set<DefaultMutableTreeNode> curNodes = new HashSet<DefaultMutableTreeNode>();
    curNodes.add(root);

    final Set<Column> keys = map.keySet();
    for (final Column key : keys) {
        final Set<Row> rowSet = map.get(key);
        Set<DefaultMutableTreeNode> tmpNodes = new HashSet<DefaultMutableTreeNode>();
        for (final Row row : rowSet) {
            DefaultMutableTreeNode curNode = new DefaultMutableTreeNode();
            curNode.setUserObject(row);
            tmpNodes.add(curNode);
            for (DefaultMutableTreeNode n : curNodes) {
                n.add(curNode);
            }
        }
        curNodes = tmpNodes;
    }
  

Я надеюсь, что это не домашнее задание какого-нибудь студента.

Во-первых, чтобы сохранить порядок ключей карты неизменным, используйте a SortedMap , like TreeMap . Кроме того, в вашей исходной карте каждая строка содержит только одно значение, например ‘abc’. Рекурсия здесь — это обход в глубину. Сложность в том, что карта не имеет естественного обхода. Для остальных есть задачи / кандидаты и задачи / результат; выполните шаг, изменяющий данные, а затем восстановите их.

Здесь я использую более известный список, но стек был бы лучше.

 public List<Row> generateRows(SortedMap<Column, Set<Cell>> map) {
    List<Row> done = new ArrayList<Row>();
    List<Column> columnsToDo = new LinkedList<Column>(map.keySet());
    List<Cell> partialRow = new LinkedList<Cell>();
    generateRowsRec(map, columnsToDo, partialRow, done);
    return done;
}
void generateRowsRec(SortedMap<Column, Set<Cell>> map, List<Column> columnsToDo, List<Cell> partialRow, List<Row> done) {
    if (columnsToDo.isEmpty()) {
        done.add(new Row(partialRow));
        return;
    }
    Column firstColumn = columnsToDo.remove(0); // Step A
    for (Cell cell : map.get(firstColumn)) {
        partialRow.add(cell); // Step B
        generateRowsRec(map, columnsToDo, partialRow, done);
        partialRow.remove(partialRow.size() - 1); // Unstep B
    }
    columnsToDo.add(0, firstColumn); // Unstep A
}