我有一个项目，我必须在其中使用 3x1 和 4.5x1 的 block 创建面板。为了结构完整性， block 之间的空间不得在相邻行中对齐。我必须计算所有可能的组合。一些示例是 7.5x1 面板有 2 种可能的解决方案，7.5x2 面板有 2 种可能的解决方案，12x3 面板有 4 种可能的方式，27x5 的面板有 7958 种可能的方式。我的问题是，当我进入更高的宽度时，我得到了比我应该得到的更多的解决方案。我认为这与我有可能得到重复表有关，但我看不到它发生在哪里或如何修复它。任何帮助将不胜感激。代码如下。

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

import puzzle.Row;

public class panel {
/**
 * This program will return the number of unique tables that for structural      integrity don't have blocks that line up
 * in adjacent rows.  The width is to be between 3 and 48 and the height between 1 and 10.  The width
 * should also be a multiple of 0.5.
 * 
 * @param width, height
 * @return totalTables
 */
public static void main(String[] args) {
    int width = 0;
    int height = 0;

    // Check to make sure that two arguments were passed.
    if (args.length != 2) {
        System.out.println("Please enter both a height and a width.");
        System.exit(1);
    } else {
        // Check that a data type of double was entered.
        if ( ( args[0].matches("^[0-9]+(\\.[0-9]+)?$") ) && 
                ( Double.valueOf(args[0].trim()).doubleValue() >= 3.0 ) && 
                ( Double.valueOf(args[0].trim()).doubleValue() <= 48.0 ) && 
                ( Double.valueOf(args[0].trim()).doubleValue()) % 0.5 == 0 ) {
            width = (int) (Double.valueOf(args[0].trim()).doubleValue() * 2); // Double the width so that we are working with an integer.
        } else {
            System.out.println("Please enter a number for your width that is between 3 and 48 and divisable by 0.5.");
            System.exit(1);
        }
        // Check that a data type of integer was entered.
        if ( ( args[1].matches("^[0-9]+$") ) && ( Integer.valueOf(args[1]) >= 1 ) && ( Integer.valueOf(args[1]) <= 10 )) {
            height = Integer.valueOf(args[1].trim()).intValue();
        } else {
            System.out.println("Please enter an integer for your height that is between 1 and 10.");
            System.exit(1);
        }

        List<Row> allRows = new ArrayList<Row>(); // Holds all the possible rows and needed information
        findAllRows(width, 0, 0, allRows);
        findMatches(allRows);
        long totalTables = findUniqueTables(allRows, height);
        System.out.println(totalTables);
    }
}

/**
 * Recursively calculates all possible row combinations for supplied width.
 * Row configuration is stored in binary format with 1 indicating gaps.  Each bit is
 * represented by 3 inches.  The bits 1, 2, nth are dropped as they are not needed.
 * 
 * i.e. width of 12 would produce
 * width = 12 * 2 = 24
 * 
 * Bricks               Binary              Stored Binary   Decimal Value
 * 6 x 6 x 6 x 6        0 1 0 1 0 1 0 1     1 0 1 0 1       21
 * 9 x 9 x 6            0 0 1 0 0 1 0 1     0 1 0 0 1       9
 * 9 x 6 x 9            0 0 1 0 1 0 0 1     0 1 0 1 0       10
 * 6 x 9 x 9            0 1 0 0 1 0 0 1     1 0 0 1 0       18
 */

public static void findAllRows(int width, int currLen, int rowConfig, List<Row> root) {
    if (currLen + 6 == width) {
        root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
        return;
    } else if (currLen + 9 == width) {
        rowConfig = rowConfig << 1;
        root.add(new Row(width, rowConfig)); // Add current row configuration as an acceptable row.
        return;
    } else if (currLen + 6 > width) {
        return; // Current configuration is longer than the width is allowed.  Do not add.
    } else {
        int nextConfig = (rowConfig << 2) + 1;  //
        findAllRows(width, currLen + 6, nextConfig, root);

        nextConfig = (rowConfig << 3) + 1;
        findAllRows(width, currLen + 9, nextConfig, root);
    }
    return;
}

/**
 * Finds all possible row matches for the given row that do not have gaps that line up.
 */
public static void findMatches(List<Row> rows) {
    for (Row row : rows) {
        for (Row rowC : rows) {
            if (matchesBelow(row.getGaps(), rowC.getGaps())) {
                row.addChilcRows(rowC.getGaps());
            }
        }
    }
}

/**
 * Does a bitwise AND to see if there are any gaps that line up.  If there are no gaps then
 * the resulting AND should equal to 0.
 */
public static boolean matchesBelow(int row, int rows) {
    if ((row & rows) == 0) {
        return true;
    } else {
        return false;
    }
}

/**
 * Finds all the unique tables and returns the count.
 */
public static long findUniqueTables(List<Row> allRows, int height) {
    long tableCount = 0;
    for (Row row : allRows) {
        tableCount += findTables(row, height);
    }
    return tableCount;
}


/**
 * This makes all possible tables.
 */
public static long findTables(Row row, int tableHeight) {
    long count;
    if (tableHeight == 1) {
        return 1;
    } else {
        count = 0;
        for (int i = 0; i < row.getChildRowsSize(row); i++) {
            count += findTables(row, tableHeight -1);
        }   
    }
    return count;
}
}

还有我的 puzzle.Row 类。

package puzzle;

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

public class Row {
int gaps;
int width;
List<Long> potChildRows = new ArrayList<Long>();

public Row(int width, int gaps) {
    this.gaps = gaps;
    this.width = width;
}

public int getGaps() {
    return this.gaps;
}

public int getWidth() {
    return this.width;
}

public long getChildRowsSize(Row row) {
    return row.potChildRows.size();
}

public void addChilcRows(long row) {
    this.potChildRows.add(row);
}
}

最佳答案

我想我刚刚完成了作业。尽管这个问题被问到已经两个月了，但我认为它看起来是一个有趣的问题，所以我试了一下。由于“家庭作业”标签(即使在 2 个月后)，我不想发布我的代码，所以我将只描述我的方法。我使用 Python，但我会尝试将任何术语翻译成 Java。

首先，我觉得您跟踪的数据比您需要的多得多。我只是保留了一个 double 的 ArrayList，这样对于任何 double i，i 都指向一个 ix1 block 。该列表的顺序是 row[0] 是最左边的 block ，row[row.length-1] 是最右边的 block 。例如，[3, 3, 4.5] 表示长度为 10.5 的行，从左到右依次使用一个 3x1 block 、另一个 3x1 block 和一个 4.5x1 block 。使用这个简单的结构，我可以轻松地可视化我的配置。我的行长度就像将所有元素加在一起一样简单(即 3 + 3 + 4.5 = 10.5)。我的差距就像在遍历我的列表时保持运行总数一样简单(即我的差距是 3 和 3 + 3 = 6)。使用这种更简单的数据类型，您可以大大简化您的代码。

此外，我发现将问题视为修改过的 Depth-First Search 会很有帮助.使用 DFS 并给定一棵二叉树，从根开始，您首先尝试向左走。然后你尝试向左走，只剩下最后一个节点。等等。而不是“左”和“右”，想想“3”和“4.5”，其中节点的值是宽度，一旦宽度变得大于所需宽度，你就停止遍历树，width。如果您找到一个值恰好为 width 的节点，则该路径现在是一个可能的行，记住它。换句话说，您先从左到右构建行，尝试 N 个 3x1 block (这样 width + 2.5 >= N*3 >= width)。然后你尝试 (N-1) 个 3x1 block 和 1 个 4x1 block (4x1 是最右边的)。然后 (N-2) 个 3x1，一个 4x1，再一个 3x1。等等。没有移位，没有 rowConfig 变量，只有 block 宽度的 ArrayList。此外，由于您系统地遍历了每条路径(即尝试了每个组合)一次且仅一次，您知道您已经尝试了每个组合并且您知道没有重复。

现在， build 你的墙。这也可以视为修改后的 DFS。想象一棵 n 叉树，其中 n 等于宽度 width 的潜在行数。使用相同的系统方法，尝试每条路径，直到得到一堵高度为 height 的墙(因为每一行的高度都是 1)。但请记住，如果没有相邻的间隙，您只想遍历一条路径。尝试从下往上一次 build 一排墙。当且仅当它的间隙都不与顶行的间隙相邻时，通过在墙的顶部添加一个新行，您可以相信您的部分墙始终有效。在那里，一旦您达到高度，您就知道您有一堵有效的墙。记录路径并继续，直到没有更多有效路径可供探索。

很抱歉在您还在做作业时没有回答。我很想知道您的最终解决方案与我的有何不同。

关于java - 带有 block 的独特面板组合 -- Java 代码，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10115906/