15,613,873 members
5.00/5 (1 vote)
See more:
I have a 10x10 integer array (call it "table"), and I have an iterative task I need to do in C++ with the array. Essentially, I need to make all possible choices of chopping the table into "districts" within the table, where by "district" I mean a collection of table entries that satisfies

1) each district consists of 10 entries of the table

2) each entry in a district is adjacent to at least one other entry in the district. That is, for each entry a_ij in the district there must be another entry in the district above, below, to the right of, or to the left of a_ij (diagonal movement doesn't count as adjacent).

What I need is to go through all possible divisions of this table into districts. So one possible division is each row is a district, another possible division is each column is a district, etc. For each possible division I have a computation I need to do but I know how to do this computation, I just don't know how to implement the marching through of all possible choices of dividing the table into districts. Is there an algorithm in the algorithm library that could help me? Or this straightforward to code from scratch? I apologize if this is a trivial question, I don't know much C++ but I need to do this for a separate project.

What I have tried:

I have tried thinking through the algorithm and trying to find something similar in the C++ algorithm library.
Posted
Updated 29-May-18 19:52pm
Comments
John R. Shaw 28-May-18 17:41pm
Sounds like it is time to break out the paper and pencil. Draw the 2 dimensional array [10x10 grid] with appropriate values, so you can visualize the problem.
Daniel Pfeffer 29-May-18 4:57am
Look at articles about polyominoes.

This sounds like a tiling problem (cover an area with tiles of differing shapes/sizes). A brute-force method would start by writing an algorithm to create all possible 10-tiles, and then writing an algorithm that tries to pack 10 of them in a particular area, but there are probably better methods of doing this.

Assume that you have any number of tiles of each shape. Don't forget rotations and mirrors of tile shapes!

## Solution 1

Here's my solution:

C++
```// ConsoleApplication3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#include <time.h>

#define N 10
#define DIST_N 10

typedef struct tagDists
{
int** dist;
int size_x;
int size_y;
bool is_d;
} DISTS, *LP_DISTS;

int main()
{
int** matrix = (int**)malloc(sizeof(int*) * N);
memset((void*)matrix, 0x00, sizeof(int*) * N);

srand((unsigned)time(nullptr));

for (int i = 0; i < N; i++)
{
matrix[i] = (int*)malloc(sizeof(int) * N);
memset((void*)matrix[i], 0x00, sizeof(int) * N);
for (int j = 0; j < N; j++)
{
matrix[i][j] = rand() % 9 + 1;
printf("%d ", matrix[i][j]);
}

printf("\n");
}

printf("\n");

int dist_size = (int)pow((double)N, 2) / DIST_N;

int dist_size_x = int(sqrt((double)dist_size));
int dist_size_y = dist_size / dist_size_x;

int n_chunks_row = int(ceil(N / (double)dist_size_x));
int n_chunks_col = int(ceil(N / (double)dist_size_y));

int n_dists = n_chunks_row * n_chunks_col;

LP_DISTS dists = (LP_DISTS)malloc(sizeof(DISTS) * n_dists);
memset((void*)dists, 0x00, sizeof(DISTS) * n_dists);

int n = 0;
for (int t1 = 0; t1 < n_chunks_row; t1++)
{
int start_x = t1 * dist_size_x;
int end_x = (t1 + 1) * dist_size_x;

start_x = (start_x > N) ? N : start_x;
end_x = (end_x > N) ? N : end_x;

for (int t2 = 0; t2 < n_chunks_col; t2++)
{
int start_y = t2 * dist_size_y;
int end_y = (t2 + 1) * dist_size_y;

start_y = (start_y > N) ? N : start_y;
end_y = (end_y > N) ? N : end_y;

dists[n].dist = (int**)malloc(sizeof(int*) * abs(start_x - end_x));

int n_i = 0;
for (int i = start_x; i < end_x; i++, n_i++)
{
dists[n].dist[n_i] = (int*)malloc(sizeof(int) * abs(start_y - end_y));

int n_j = 0;
for (int j = start_y; j < end_y; j++, n_j++)
dists[n].dist[n_i][n_j] = matrix[i][j];
}

dists[n].is_d = false;
dists[n].size_x = abs(start_x - end_x);
dists[n].size_y = abs(start_y - end_y);

n++;
}
}

for (int t = 0; t < n_dists; t++)
{
if ((dists[t].size_x < dist_size_x) ||
(dists[t].size_y < dist_size_y))
{
int n_items = dists[t].size_x * dists[t].size_y;
int items_per_dist = int(ceil(n_items / ((double)dist_size_x * dist_size_y)));

int* v = (int*)malloc(sizeof(int) * dists[t].size_x * dists[t].size_y);
memset((void*)v, 0x00, sizeof(int) * dists[t].size_x * dists[t].size_y);

int n = 0;
for (int s1 = 0; s1 < dists[t].size_x; s1++)
for (int s2 = 0; s2 < dists[t].size_y; s2++)
v[n++] = dists[t].dist[s1][s2];

for (int i = 0, n = 0; i < n_dists && n_items > 0; i++)
{
if ((dists[i].size_x >= dist_size_x) &&
(dists[i].size_y >= dist_size_y) && i != t)
{
if (dists[i].size_x * dists[i].size_y < dist_size)
{
dists[t].is_d = true;

int rows = int(ceil(items_per_dist / (double)N));
dists[i].dist = (int**)realloc(dists[i].dist, sizeof(int) * rows * dists[i].size_y);

dists[i].size_x += rows;

int i2 = dists[t].size_x;
for (int i1 = dists[i].size_x - rows; i1 < dists[i].size_x && --i2 >= 0; i1++)
{
int j2 = dists[t].size_y;
dists[i].dist[i1] = (int*)malloc(sizeof(int) * dists[i].size_y);
memset((void*)dists[i].dist[i1], 0x00, sizeof(int) * dists[i].size_y);
for (int j1 = 0; j1 < dists[i].size_y && --j2 >= 0; j1++)
{
dists[i].dist[i1][j1] = v[n++]; n_items--;
}
}
}
}
}
}
}

int* v = (int*)malloc(sizeof(int) * dist_size);
memset((void*)v, 0x00, sizeof(int) * dist_size);

int r = 0;
for (int t = 0; t < n_dists; t++)
{
if ((dists[t].size_x < dist_size_x) ||
(dists[t].size_y < dist_size_y))
{
if (dists[t].is_d == false)
{
for (int i = 0; i < dists[t].size_x && i < N; i++)
for (int j = 0; j < dists[t].size_y && j < N; j++)
v[r++] = dists[t].dist[i][j];
}
}
}

int** dist = (int**)malloc(sizeof(int*) * dist_size_x + 1);
memset((void*)dist, 0x00, sizeof(int*) * dist_size_x + 1);

for (int i = 0, r = 0; i < dist_size_x; i++)
{
dist[i] = (int*)malloc(sizeof(int) * dist_size_y);
memset((void*)dist[i], 0x00, sizeof(int) * dist_size_y);
for (int j = 0; j < dist_size_y; j++)
dist[i][j] = v[r++];
}

dist[dist_size_x] = (int*)malloc(sizeof(int) * dist_size_y);
memset((void*)dist[dist_size_x], 0x00, sizeof(int) * dist_size_y);

dist[dist_size_x][0] = v[r - 1];

int x = 0;
for (int t = 0; t < n_dists; t++)
{
if ((dists[t].size_x >= dist_size_x) &&
(dists[t].size_y >= dist_size_y))
{
if (dists[t].is_d == false)
{
printf("District: %d\n", x + 1);

for (int i = 0; i < dists[t].size_x && i < N; i++)
{
for (int j = 0; j < dists[t].size_y && j < N; j++)
printf("%d ", dists[t].dist[i][j]);

printf("\n");
}

printf("\n");

x++;
}
}
}

printf("District: %d\n", x + 1);

for (int i = 0; i < dist_size_x + 1; i++)
{
for (int j = 0; j < dist_size_y; j++)
printf("%d ", dist[i][j]);

printf("\n");
}

printf("\n");

return 0;
}```

Comments
[no name] 30-May-18 3:14am
It's a pity you did not add comments to the code. Anyway, great commitment to help!
Arthur V. Ratz 30-May-18 3:21am
I'm just a little bit busy right at this moment, that's why I've not written and added comments to my code. I'm sorry, I'm about to add some comments later on. Anyway, thanks for your comment. :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 Graeme_Grant 60 OriginalGriff 50 CPallini 50 CHill60 40 Chris Copeland 30
 OriginalGriff 2,856 Richard MacCutchan 1,226 Graeme_Grant 940 Dave Kreskowiak 641 CPallini 330

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900