Finding all partitions of a grid into k connected components

I am working on floor planing on small orthogonal grids. I want to partition a given $ m \times n$ grid into $ k$ (where $ k \leq nm$ , but usually $ k \ll nm$ ) connected components in all possible ways so that I can compute a fitness value for each solution and pick the best one. So far, I have the fitness evaluation at the end of the algorithm, no branch-and-bound or other type of early-termination, since the fitness computation requires the complete solution.

My current approach to listing all possible grid partitions into connected components is quite straight forward and I am wondering what optimizations can be added to avoid listing duplicate partitions? There must be a better way than what I have right now. I know the problem is NP, but I would at like to push my algorithm from brute-force to a smart and efficient approach.

Overview

For better visualization and description I will reformulate the task to an equivalent one: paint the grid cells using $ k$ colors so that each color builds a single connected component (with respect to 4-neighborhood) and of course all grid is completely painted.

My approach so far:

  1. Generate all seed scenarios. A seed scenario is a partial solution where each color is applied to a single cell only, the remaining cells are yet empty.
  2. Collect all possible solutions for each seed scenario by expanding the color regions in a DFS manner.
  3. Filter out duplicate solutions with help of a hash-table.

Seed scenarios

I generate the seed scenarios as permutations of $ k$ unique colors and $ mn-k$ void elements (without repetition of the voids). Hence, the total number is $ (nm)! / (mn-k)!$ For example, for a $ 1 \times 4$ grid and colors $ {0, 1}$ with void denoted as $ \square$ the seed scenarios are:

  • $ [0 1 \square \square]$
  • $ [0 \square 1 \square]$
  • $ [0 \square \square 1]$
  • $ [1 0 \square \square]$
  • $ [1 \square 0 \square]$
  • $ [1 \square \square 0]$
  • $ [\square 0 1 \square]$
  • $ [\square 0 \square 1]$
  • $ [\square 1 0 \square]$
  • $ [\square 1 \square 0]$
  • $ [\square \square 0 1]$
  • $ [\square \square 1 0]$

Seed growth / multicolor flood-fill

I assume the painting to be performed in a fixed ordering of the colors. The seed scenario always comes with the first color set as the current one. New solutions are generated then either by switching to the next color or by painting empty cells by the current color.

//PSEUDOCODE buffer.push(seed_scenario with current_color:=0); while(buffer not empty) {     partial_solution := buffer.pop();     if (partial_solution.available_cells.count == 0)         result.add(partial_solution);     else     {         buffer.push(partial_solution.nextColor()); //copy solution and increment color         buffer.pushAll(partial_solution.expand()); //kind-of flood-fill produces new solutions     } } 

partial_solution.expand() generates a number of new partial solutions. All of them have one additional cell colored by the current color. It examines the current region boundary and tries to paint each neighboring cell by the current color, if the cell is still void.

partial_solution.nextColor() duplicates the current partial solution but increments the current painting color.

This simple seed growth enumerates all possible solutions for the seed setup. However, a pair of different seed scenarios can produce identical solutions. There are indeed many duplicates produced. So far, I do not know how to take care of that. So I had to add the third step that filters duplicates so that the result contains only distinct solutions.

Question

I assume there should be a way to get rid of the duplicates, since that is where the efficiency suffers the most. Is it possible to merge the seeds generation with the painting stage? I started to thing about some sort of dynamic programming, but I have no clear idea yet. In 1D it would be much easier, but the 4-connectivity in a 2D grid makes the problem much harder. I tried searching for solutions or publications, but didn’t find anything useful yet. Maybe I am throwing in the wrong keywords. So any suggestions to my approach or pointers to literature are very much appreciated!

Note

I found Grid Puzzle Split Algorithm, but not sure if the answers can be adapted to my problem.

Proving injectivity for an algorithm computing a function between sets of different types of partitions [closed]

I am attempting to solve the following problem:

Let $ A$ be the set of partitions of $ n$ with elements $ (a_1, \dots, a_s)$ such that $ a_i > a_{i+1}+a_{i+2}$ for all $ i < s,$ taking $ a_{s+1} = 0.$ Define $ g_n = F_{n+2}-1$ and let $ B$ be the set of partitions of $ n$ as $ b_1 \ge \dots \ge b_s$ such that $ b_i \in \{g_n\}$ for all $ i,$ and if $ b_1 = g_k$ for some $ k,$ then $ g_1, \dots, g_k$ all appear as some $ b_i.$ Prove $ |A|=|B|.$

Attempt: Let $ e_i$ be the vector with $ 1$ at position $ i$ and $ 0$ elsewhere. If $ b_1 = g_k,$ let $ c=(c_k, \dots, c_1)$ count how many times $ g_i$ appears. We calculate $ f: B \to A$ as follows:

Let $ c=(c_k,\dots,c_1), a=(0,\dots,0).$ While $ c \ne 0,$ let $ d_1 > \dots > d_k$ be the indices such that $ c_{d_i} \ne 0.$ Replace $ c, a$ with $ c-(e_{d_1}+\dots+e_{d_k}), a+(g_{d_1} e_1 + \dots + g_{d_k} e_k)$ respectively. After the while loop ends, let $ f(b)=a.$

Let $ \sum a, \sum b, \sum c$ be the sum of the components of $ a, b, c$ respectively. Since $ \sum c$ decreases after every loop, the algorithm terminates and $ f(b)$ is well-defined. Since $ c_k g_k + \dots + c_1 g_1 + \sum a$ does not change after every iteration, is $ \sum b$ at the start and $ \sum a$ at the end, we have $ \sum f(b) = \sum b = n,$ so $ f(b)$ is also a partition of $ n.$ Now $ a = (g_k, \dots, g_1)$ after the first loop, which satisfies the condition $ g_i > g_{i-1}+g_{i-2}$ since $ g_i = F_{n+2}-1 = (F_{n+1}-1)+(F_n-1)+1 > g_{i-1}+g_{i-2}.$ Furthermore, after every iteration of the loop, the difference $ a_i – (a_{i-1}+a_{i-2})$ changes by $ 0, g_{d_j}-g_{d_{j-1}} > 0,$ or $ g_{d_j}-(g_{d_{j-1}}+g_{d_{j-2}}) > 0,$ so we have $ a_i > a_{i-1} + a_{i-2}$ at the end and hence $ f(b) \in A.$ Thus, $ f: B \to A$ is well-defined.

In order to prove the injectivity of $ f,$ it suffices to prove each loop iteration as a mapping $ (c,a) \to (c’,a’)$ is injective, which would imply the mapping $ (c,0) \to (0,a)$ that the while loop creates is injective. Indeed, if $ f(b_1) = f(b_2) = a$ with $ (c_1, 0), (c_2, 0)$ being sent to $ (0, f(b_1)) = (0,a), (0, f(b_2)) = (0,a)$ respectively, then we have $ (c_1, 0) = (c_2, 0) \Rightarrow c_1 = c_2 \Rightarrow b_1 = b_2.$

Suppose $ d_1 > \dots > d_i, f_1 > \dots > f_j$ are the non-zero indices of $ c_1, c_2$ respectively and $ c_1 – (e_{d_1}+\dots+e_{d_i}) = c_2 – (e_{f_1}+\dots+e_{f_j}), a_1+g_{d_1}e_1 + \dots+ g_{d_i} e_i = a_2 + g_{f_1} e_1 + \dots + g_{f_j} e_j.$ If $ x \ge 2$ is an entry of $ c_1,$ it decreases by $ 1,$ so the corresponding entry in $ c_2$ after $ c_2$ is modified is also $ x-1,$ which means it must’ve been $ (x-1)+1 = x$ before since $ x-1>0.$ Thus, if the values of two positions of $ c_1, c_2$ differ, one is $ 1$ and the other is $ 0.$ However, if $ c_1 = (1,0), a_1 = (3,1), c_2 = (0,1), a_2 = (4,1),$ then $ (a_1, c_1), (a_2, c_2)$ both get sent to $ ((5,1), (0,0)).$ I can rule out this specific example by arguing that one of the pairs is illegal and could not have come from any choice of initial $ c,$ but I have no idea on how to do this in general.

What should I do next in order to show $ f$ is injective? Furthermore, since the problem I’m trying to prove is correct, injectivity would imply $ f$ is secretly a bijection. But I have no clue on how to even start on the surjectivity of $ f,$ so I just constructed a similar algorithm for $ g: A \to B$ in the hopes of proving $ g$ is injective too. If I can show $ f$ is injective I will probably know how to show $ g$ is.

Here is an example of $ f, g$ in practice:

Let $ n = 41, b = (12, 7, 7, 4, 4, 2, 2, 2, 1) \Rightarrow c = (1, 2, 2, 3, 1).$

$ $ ((1, 2, 2, 3, 1), (0,0,0,0,0)) \to ((0, 1, 1, 2, 0), (12, 7, 4, 2, 1)) \to ((0, 0, 0, 1, 0), (19,11,6,2,1)) \to ((21,11,6,2,1),(0,0,0,0,0)),$ $ so $ f(b) = (21,11,6,2,1).$

Let $ a = (21, 11, 6, 2, 1).$

$ $ ((21,11,6,2,1),(0,0,0,0,0)) \to ((9,4,2,0,0), (1,1,1,1,1)) \to ((2,0,0,0,0),(1,2,2,2,1)) \to ((0,0,0,0,0),(1,2,2,3,1)),$ $ so $ g(a) = (12, 7, 7, 4, 4, 2, 2, 2, 1).$

Difficulty understanding Algorithm to print Partitions of a Number [on hold]

Here’s a code I came across, which aims to print the partitions of a given number $ n$

I am unable to understand how the code accomplishes what it does, i.e. I’ve difficulty in understanding the algorithm. How does the code work?

#include <stdio.h> #include <string.h> #include <math.h> // Take a number and print it textually // For non-positive numbers it returns the empty string void itoa(int n, char *str){ if(n <= 0){     str[0] = '';     return; } int i, len = floor(log10(n) + 1); // number of digits in n for(i = len - 1; i >= 0; i--){     str[i] = '0' + (n % 10);     n /= 10; } str[len] = ''; }  // n tell us which number is to be partitioned // next tells us the location in the string where to print next // min tell us the minimum number we must choose next void partition(char *str, int n, int next, int min){ if(n == 0){     str[next] = '';     printf("%s\n", str);     return; } int i; // If this is not the first number in the partition // we need a plus sign before we print the next number if(next)     str[next++] = '+'; // Start from min so that numbers in a partition are always // in a non-decreasing order. This ensures that we will never // repeat a partition twice for(i = min; i <= n; i++){     itoa(i, str + next);     // We have already absorbed i so now partitions of n-i needed     // All future numbers in this partition must be at least i     partition(str, n - i, next + strlen(str + next), i); } }  int main(){ char str[1000]; // This code will output partitions in lexicographically increasing // order. However, lexicographic order means something a bit different // for this code. Nevertheless, no partition will be repeated twice. int n; scanf("%d",&n); // This code can handle any positive number, with any number of digits,  // so long as writing the parition does not take more than 999 chars partition(str,n, 0, 1); return 0; } 

Any and all help will be appreciated. Thank you!

Install alongside win7 what partitions do I need to set?

I’ve got a 40gb unallocated partition on my c: drive. Might be a bit much but it’s ok.
I’m looking to install Ubuntu 19 I’ve seen on some guides that I need to define swap and root stuffs. I’m a linux baby so I really don’t know whats actually needed.
Definitive answer?
16gb Ram, not worried about hibernate if that matters.

Are the partitions totally separate when using dual boot?

I currently have a PC with Windows 10 and a 1 TB SSD. I’m planning on partitioning the disk and installing Ubuntu on the other partition, so that I can have dual boot. My question is; are the partitions totally separate? Meaning that if I’m running my PC with Windows on partition A, do I have access to the files stored on partition B where Ubuntu is installed? And likewise, say I create a .java file for work while working on Ubuntu on partition B, can I store this file on partition A and have access to this no matter which OS I’m currently on?

Will it matter where my files (not OS) are stored, so I should consider this when choosing the size of my partitions?

Installing Ubuntu: cannot disable fast boot and no partitions showing

I’m trying to install Ubuntu 18.04 (dual boot / alongside Windows) on my Lenovo Yoga 520 with the InsydeH20 BIOS Setup Utility, but I have the following problems:

  1. I cannot disable fast boot. I know that disabling the option is needed for a correct installation, but disabling it in the boot menu has no effect. Turning off the computer and checking the boot menu again yields seeing the “Fast boot” option as active (the BIOS battery should not be dead as other options survive)

  2. The installer sees no partitions. When trying to install the OS, the installer doesn’t show me any partitions to select.

I managed to fix one problem though: I used to get the error “MODSIGN: Couldn’t get UEFI db list” but managed to “fix” it by resetting some keys in the boot menu (now I only get the error “Couldn’t get size: 0x000…”).

I have already disabled fast startup in Windows but it doesn’t seem to have any effect as can be seen here… My only idea for the cause would a broken hybernation file.

I accept any advice, thank you in advance.

If I delete all partitions during Ubuntu installation and create efi partition, will I need to update firmware?

I am installing Ubuntu 19.04 on laptop(it has SSD drive) that comes with Free DOS predinstalled. I set BIOS to boot as uefi and I will delete all current partitions and create efi (with boot flag), root and home. Will everything be OK or, I will need to update firmware. Thank you in advance.

Parted saying “cant have overlapping partitions” but no partitions overlap

Image of issue

Hello all, I am having an issue with my raspberry pi. I am trying to move it from one sd card to another larger one,and when I resizepart it says there is an overlapping partition, but I do not see one. Is there something i am missing?

Log:

(parted) print free Model: Generic STORAGE DEVICE (scsi) Disk /dev/sda: 128GB Sector size (logical/physical): 512B/512B Partition Table: msdos Disk Flags:  Number  Start   End     Size    Type      File system  Flags         32.3kB  4194kB  4162kB            Free Space  1      4194kB  1936MB  1932MB  primary   fat32        lba  2      1936MB  15.9GB  14.0GB  extended  5      1938MB  1971MB  33.6MB  logical   ext4  6      1971MB  2044MB  72.4MB  logical   fat32        lba  7      2047MB  15.0GB  13.0GB  logical   ext4         15.0GB  15.9GB  932MB             Free Space         15.9GB  128GB   112GB             Free Space  (parted) resizepart 7 End?  [15.0GB]? 100.0GB Error: Can't have overlapping partitions. (parted) 

Removing Old Partitions

I’m trying to wipe data from an old drive but no matter what I do, the partitions seem to remain. When applying the changes after removing the partitions, gParted gives errors, then shows the full unallocated area but afterward when it finishes its scan, the partitions have returned. How can I get rid of them? The drive itself is being accessed using a USB “toaster” that I always use when managing separate drives.

How can I protect my linux partitions against corruption by Ext2Read?

I have 2 disks. The first one contains my ubuntu main OS, along with another partition where GRUB is located.

Another disk has a windows 10 installed with an utility, Ext2Read, installed as a service to read ext partitions (i.e. the ubuntu one)

Each time I boot on windows, the ext2read service mount my ubuntu partition and thus corrupt it. When I reboot on Ubuntu, I have superblock issues, and have to repair the disk.

Last time, I couldn’t fix it without using a live CD and several tools to repair everything, not to mention that I am no expert on the matter and often might not make the best repair choices.

I need that windows OS for CAD purposes, and my original idea was to unplug the Ubuntu disk before booting, but then I do not have grub and nothing to boot on.

What could I do to fix this, ideally without reinstalling a fresh windows? Can I somehow either protect the linux partitions, or boot without grub on windows, in order to remove that Ext2Read software & service?

Feel free to request any additional info on my system.

Thanks!