高效地計算行中給定「塊」集合的排列

我正在研究一個應用程序，其中應有一些塊應位於一行上。即有不同數量的塊，每塊有不同的長度，應該放在線上。塊之間至少需要有一個空元素。高效地計算行中給定「塊」集合的排列

我想有效地獲得所有可能的排列在線上的塊。

例如，我有一個長度爲15的行，並希望放置1,6和1大小的塊。

訂單很重要，例如，在我的示例中，1尺寸塊總是應該在6尺寸塊的左側和右側。

可能的排列是

X.XXXXXX.X..... 
X..XXXXXX.X.... 
... 
.....X.XXXXXX.X

如何高效地產生更高層次的語言，例如所有可能的排列Java的？要做到這一點

來源

2013-01-03 centic

出於好奇，這是nonograms？ – templatetypedef

是的，我在玩 – centic

一種方法是遞歸來解決：

如果所需的最小總長度所有的塊存儲可以精確到一個空間，它們之間超過了可用空間，有沒有辦法放置塊。
否則，如果你沒有塊放置，那麼放置塊的唯一方法是讓所有的方塊都沒有填充。
否則，有兩種選擇。首先，您可以將第一個塊放置在該行的第一個位置，然後遞歸地將剩餘的塊放置在行的剩餘空間中，然後在該行的開始處首先留下一個額外的空白空間。其次，您可以將行中的第一個空格留空，然後遞歸地將同一組塊放入行中的剩餘空間。嘗試兩種選擇並將結果合併到一起應該會給你你正在尋找的答案。

將此遞歸邏輯轉換爲實際的Java應該不會太困難。下面的代碼是專爲可讀性和可優化的一點：

public List<String> allBlockOrderings(int rowLength, List<Integer> blockSizes) { 
    /* Case 1: Not enough space left. */ 
    if (spaceNeededFor(blockSizes) > rowLength)) return Collections.EMPTY_LIST; 

    List<String> result = new ArrayList<String>(); 

    /* Case 2: Nothing to place. */ 
    if (blockSizes.isEmpty()) { 
     result.add(stringOf('.', rowLength)); 
    } else { 
     /* Case 3a: place the very first block at the beginning of the row. */ 
     List<String> placeFirst = allBlockOrderings(rowLength - blockSizes.get(0) - 1, 
                blockSizes.subList(1, blockSizes.length())); 
     for (String rest: placeFirst) { 
      result.add(stringOf('X', blockSizes.get(0)) + rest); 
     } 

     /* Case 3b: leave the very first spot open. */ 
     List<String> skipFirst = allBlockOrderings(rowLength - 1, blockSizes); 
     for (String rest: skipFirst) { 
      result.add('.' + rest); 
     } 
    } 
    return result; 
}

你需要實現spaceNeededFor方法，它返回那些可能持有塊的給定列表最短行的長度，和接收字符和數字的stringOf方法會返回給定字符的許多副本的字符串。

希望這會有所幫助！

來源

2013-01-03 09:24:08 templatetypedef

沒有明確得到第三點..請詳細說明一下吧 –

@ ShivaKomuravelly-試着想想你要把第一塊放在哪裏。它要麼在第一個地方，要麼就離開第一個地方。如果您嘗試使用這兩個選項（將第一個塊放在行的開頭，或者在行的開始處打開空間），然後將所有剩餘的塊遞歸放置在未使用的空間中，您將生成所有可能的放置位置。另外，如果有幫助，我添加了一些代碼。 – templatetypedef

謝謝，我會嘗試編碼它類似於此，並會報告回來，如果它的工作 – centic

很難確定什麼是「高效實現」，因爲輸出可能非常大，因此即使快速實現也不夠快。

我會使用這種任務的動態編程和遞歸技術。遞歸函數應該有兩個參數 - 未使用的數字列表和行的剩餘長度。它內部將是一個簡單的循環。你應該存儲你已經知道的結果。我相信你可以自己處理細節。編輯：我們的朋友已經爲你做了這件事:-)。

順便說一下，這樣的任務的目標是什麼？它重新描述了網格中的圖片，其中每行和每列都有這樣的數字，並且您需要對圖片進行解碼。有更好的方法來解決這個問題。

來源

2013-01-03 09:30:41 Danstahr

對我來說，似乎更容易想到另一種方式的問題：

我們有固定塊在固定的順序，用點分隔。我們可以通過將剩餘的點分佈在允許的位置上來創建所有排列。

線的該固定部分的長度是：

fixed_len = length_of_all_blocks + number_of_blocks - 1

其餘的點的數目是

free_dots = length_of_line - fixed_len.

打開位置的數量是

pos_count = number_of_blocks + 1

現在我們必須找到如何將free_dots放入pos_count的所有排列組合。

來源

2013-01-03 09:50:42

這裏'free_dots'包含那些介於兩者之間的點...對嗎？ –

我試過了，它不工作 –

@ ShivaKomuravelly-這聽起來像是一個很好的解決方案。您的實施中可能存在某個錯誤。 – templatetypedef

高效地計算行中給定「塊」集合的排列

回答

相關問題