# Some kind of sorting matching pairs problem

This topic is 732 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have an array of pairs, e.g.

1:(1,2)

2:(0,0)

3:(3,1)

4:(1,3)

5:(2,3)

the pair number is integer and always less than 4.

Lets call the first number 'new slot', and the second 'old slot'.

Counting how often each value appears per slot i get

(1,2,1,1) for the new slots, and

(1,1,0,2) for the old slots. Let's call this 'slot count'.

Now, starting from the beginning of the array i want to change the new slot values to match the old values, but the resulting slot count should stay the same.

Doing this by hand i get:

(2,2) by taking the 2 from the fifth pair (and putting the 1 to a 'available count')

(0,0) already matches, so nothing to do

(1,1) by taking the 1 from either 3rd pair or the available count (and putting the 3 to a 'available count')

(X,3) There is no 3 - neither in old slot count nor in available count, so what should i do? I can leave it at (1,3), but only in case the 1 has not been taken from a previous pair, which is the case for this example.

(3,3) There is 3 on the available count, put it from there

Excluding the X i get resulting new slot count of:

(1,1,1,1)

So it is clear that step 4 must use a 1 and my assumption of (1,3) was correct and i finally get

(1,2,1,1)

Looks easy but i was only able to get an algorithm that solves the problem correctly for binary slot values.

And to be honest i do not fully understand how the algorithm works, why it fails on more slot possibilities, and if it calculates the best possible result (good result may do it for me).

Also i hope for a algorithm that knows anything before entering the loop, so it can be parallelized on GPU.

Maybe you guys know of similar problems already solved or you have bigger brains than me, feeling a bit dump now.

Thanks for reading up to here :)

Here is my solution for the binary case:

static void TestMatching ()
{
int const count = 32;

int data[count];
for (int i=0; i<count; i++)
{
int a = PRN::randI2(i*27) % 2; // % 4; //
int b = PRN::randI2(i*7) % 2; // % 4; //
data[i] = (a<<4) | b;
}

SystemTools::Log ("\nTestMatching\n\n");

int oldCount[4] = {0,0,0,0};
int newCount[4] = {0,0,0,0};
int matchCount[4] = {0,0,0,0};

for (int i=0; i<count; i++)
{
int newLod = data[i] & 3;
int oldLod = (data[i]>>4) & 3;

SystemTools::Log ("%i: (o%i n%i)  m%i\n", i, oldLod, newLod, oldLod==newLod);

oldCount[oldLod]++;
newCount[newLod]++;
if (newLod==oldLod) matchCount[newLod]++;
}

int available[4];
for (int i=0; i<4; i++) available[i] = min(newCount[i], oldCount[i]) - matchCount[i];

SystemTools::Log ("oldCount: %i %i %i %i\n", oldCount[0], oldCount[1], oldCount[2], oldCount[3]);
SystemTools::Log ("newCount: %i %i %i %i\n", newCount[0], newCount[1], newCount[2], newCount[3]);
SystemTools::Log ("matchCnt: %i %i %i %i\n", matchCount[0], matchCount[1], matchCount[2], matchCount[3]);
SystemTools::Log ("availabl: %i %i %i %i\n", available[0], available[1], available[2], available[3]);

for (int i=0; i<count; i++)
{
int newLod = data[i] & 3;
int oldLod = (data[i]>>4) & 3;

if (newLod != oldLod)
{
if (available[oldLod] > 0)
{
available[oldLod]--;

SystemTools::Log ("%i from %i to %i | avail:  %i %i %i %i  \n", i, newLod, oldLod,
available[0], available[1], available[2], available[3]);

newLod = oldLod;
}
}

data[i] = (oldLod<<4) | newLod;
}

if (1) // proof
{
int oldCount[4] = {0,0,0,0};
int newCount[4] = {0,0,0,0};
int matchCount[4] = {0,0,0,0};

for (int i=0; i<count; i++)
{
int newLod = data[i] & 3;
int oldLod = (data[i]>>4) & 3;

SystemTools::Log ("%i: (o%i n%i)  d%i\n", i, oldLod, newLod, oldLod==newLod);

oldCount[oldLod]++;
newCount[newLod]++;
if (newLod==oldLod) matchCount[newLod]++;
}

SystemTools::Log ("\noldCount: %i %i %i %i\n", oldCount[0], oldCount[1], oldCount[2], oldCount[3]);
SystemTools::Log ("newCount: %i %i %i %i\n", newCount[0], newCount[1], newCount[2], newCount[3]); // this should match the previous values
SystemTools::Log ("matchCnt: %i %i %i %i\n", matchCount[0], matchCount[1], matchCount[2], matchCount[3]); // should be higher
SystemTools::Log ("availabl: %i %i %i %i\n\n\n", available[0], available[1], available[2], available[3]);
}
}
/*
output:

0: (o0 n0)  m1
1: (o1 n1)  m1
2: (o1 n0)  m0
3: (o1 n1)  m1
4: (o1 n0)  m0
5: (o0 n1)  m0
6: (o0 n1)  m0
7: (o1 n1)  m1
8: (o0 n1)  m0
9: (o1 n1)  m1
10: (o0 n1)  m0
11: (o1 n0)  m0
12: (o0 n1)  m0
13: (o1 n1)  m1
14: (o1 n0)  m0
15: (o1 n0)  m0
16: (o1 n0)  m0
17: (o0 n0)  m1
18: (o0 n0)  m1
19: (o0 n1)  m0
20: (o1 n1)  m1
21: (o0 n0)  m1
22: (o1 n1)  m1
23: (o1 n1)  m1
24: (o1 n1)  m1
25: (o0 n0)  m1
26: (o1 n1)  m1
27: (o0 n1)  m0
28: (o0 n1)  m0
29: (o0 n0)  m1
30: (o1 n1)  m1
31: (o0 n1)  m0
oldCount: 15 17 0 0
newCount: 12 20 0 0
matchCnt: 6 11 0 0
availabl: 6 6 0 0
2 from 0 to 1 | avail:  6 5 0 0
4 from 0 to 1 | avail:  6 4 0 0
5 from 1 to 0 | avail:  5 4 0 0
6 from 1 to 0 | avail:  4 4 0 0
8 from 1 to 0 | avail:  3 4 0 0
10 from 1 to 0 | avail:  2 4 0 0
11 from 0 to 1 | avail:  2 3 0 0
12 from 1 to 0 | avail:  1 3 0 0
14 from 0 to 1 | avail:  1 2 0 0
15 from 0 to 1 | avail:  1 1 0 0
16 from 0 to 1 | avail:  1 0 0 0
19 from 1 to 0 | avail:  0 0 0 0
0: (o0 n0)  d1
1: (o1 n1)  d1
2: (o1 n1)  d1
3: (o1 n1)  d1
4: (o1 n1)  d1
5: (o0 n0)  d1
6: (o0 n0)  d1
7: (o1 n1)  d1
8: (o0 n0)  d1
9: (o1 n1)  d1
10: (o0 n0)  d1
11: (o1 n1)  d1
12: (o0 n0)  d1
13: (o1 n1)  d1
14: (o1 n1)  d1
15: (o1 n1)  d1
16: (o1 n1)  d1
17: (o0 n0)  d1
18: (o0 n0)  d1
19: (o0 n0)  d1
20: (o1 n1)  d1
21: (o0 n0)  d1
22: (o1 n1)  d1
23: (o1 n1)  d1
24: (o1 n1)  d1
25: (o0 n0)  d1
26: (o1 n1)  d1
27: (o0 n1)  d0
28: (o0 n1)  d0
29: (o0 n0)  d1
30: (o1 n1)  d1
31: (o0 n1)  d0

oldCount: 15 17 0 0
newCount: 12 20 0 0
matchCnt: 12 17 0 0
availabl: 0 0 0 0
*/



##### Share on other sites

If the frequency counts for your old slot values and new slot values aren't equal, then there will be no solution that meets your criteria of equal frequencies *and* equal slot values. You'll have to compromise on one or the other, and then choose a heuristic function that optimizes your results by determining which solutions or slot value states are "better" than others.

You described your process as starting from the beginning of the array, which would lead me to believe that matches at lower array indices are more important than matches at higher array indices; that's a good place to start.

EDIT: And if you could describe the real problem you're trying to solve with this algorithm, we may be able to provide another approach completely.

Edited by Zipster

##### Share on other sites

If the frequency counts for your old slot values and new slot values aren't equal, then there will be no solution that meets your criteria of equal frequencies *and* equal slot values. You'll have to compromise on one or the other, and then choose a heuristic function that optimizes your results by determining which solutions or slot value states are "better" than others. You described your process as starting from the beginning of the array, which would lead me to believe that matches at lower array indices are more important than matches at higher array indices; that's a good place to start. EDIT: And if you could describe the real problem you're trying to solve with this algorithm, we may be able to provide another approach completely.

Yes, i did not make that clear: The swaps should happen the most the beginning of the array - as much as possible, and at the and of the array the values should not change.

The diffulicty is to calculate how much swaps can be done.

It's for real time global illumanation where i can't update entire surface area each frame und use a fixed amount of random samples instead.

But if some big change happens (e.g. instantly turning all lights off), the system decides to update more samples at less detail to be more responsive with equal performance.

The problem is, changing detail also changes the resulting received light slightly, leading to error feedback and never stopping changing detail levels even if lighting and scene does not change.

By matching LODs with the previous frame i can reduce those LOD changes so the system converges and returns to the state of updating a small amount of samples at full detail.

So the array is coarsely sorted by the change in received light.

At the beginning are samples with small change, so more likely to converge and i try to stabilize them.

At the end are samples with big change, unlikely to converge so changing LOD will hurt less.

So other approaches are possible, and there is no need for a somehow exact solution or to define any constraints more precisely.

Currently i do some approximization and limit errors in a following step, but i think this needs improvement.

##### Share on other sites

Ok, i have it (but not sure if it gives the best solution).

Trick was to use a 2D array for the available swap count for each possible each pair:

static void TestMatching ()
{
int const count = 32;
int data[count];
for (int i=0; i<count; i++)
{
int a = PRN::randI2(i*27) % 4;
int b = PRN::randI2(i*7) % 4;
data[i] = (a<<4) | b;
}

SystemTools::Log ("\nTestMatching\n\n");

if (1) // proof
{
SystemTools::Log ("\nInitial:\n");

int oldCount[4] = {0,0,0,0};
int newCount[4] = {0,0,0,0};
int matchCount[4] = {0,0,0,0};

for (int i=0; i<count; i++)
{
int newLod = data[i] & 3;
int oldLod = (data[i]>>4) & 3;

SystemTools::Log ("%i: (o%i n%i)  m%i\n", i, oldLod, newLod, oldLod==newLod);

oldCount[oldLod]++;
newCount[newLod]++;
if (newLod==oldLod) matchCount[newLod]++;
}

SystemTools::Log ("\noldCount: %i %i %i %i\n", oldCount[0], oldCount[1], oldCount[2], oldCount[3]);
SystemTools::Log ("newCount: %i %i %i %i\n", newCount[0], newCount[1], newCount[2], newCount[3]); // this should match the previous values
SystemTools::Log ("matchCnt: %i %i %i %i\n\n", matchCount[0], matchCount[1], matchCount[2], matchCount[3]); // should be higher
}

int pairCount[4][4] = {0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0};

for (int i=0; i<count; i++)
{
int newLod = data[i] & 3;
int oldLod = (data[i]>>4) & 3;
pairCount[oldLod][newLod]++;
}

//int available[4];
int availablePairs[4][4];

for (int i=0; i<4; i++)
{
//available[i] = min(newCount[i], oldCount[i]) - matchCount[i];
for (int j=0; j<4; j++) availablePairs[i][j] = min(pairCount[i][j], pairCount[j][i]);
}

SystemTools::Log ("pairCount:      %i %i %i %i  %i %i %i %i  %i %i %i %i  %i %i %i %i  \n\n",
pairCount[0][0], pairCount[0][1], pairCount[0][2], pairCount[0][3],
pairCount[1][0], pairCount[1][1], pairCount[1][2], pairCount[1][3],
pairCount[2][0], pairCount[2][1], pairCount[2][2], pairCount[2][3],
pairCount[3][0], pairCount[3][1], pairCount[3][2], pairCount[3][3]);
SystemTools::Log ("availablePairs: %i %i %i %i  %i %i %i %i  %i %i %i %i  %i %i %i %i  \n\n",
availablePairs[0][0], availablePairs[0][1], availablePairs[0][2], availablePairs[0][3],
availablePairs[1][0], availablePairs[1][1], availablePairs[1][2], availablePairs[1][3],
availablePairs[2][0], availablePairs[2][1], availablePairs[2][2], availablePairs[2][3],
availablePairs[3][0], availablePairs[3][1], availablePairs[3][2], availablePairs[3][3]);

for (int i=0; i<count; i++)
{
int newLod = data[i] & 3;
int oldLod = (data[i]>>4) & 3;

if (newLod != oldLod)
{
if (
//(available[oldLod] > 0) // ok for binary
availablePairs[oldLod][newLod] > 0
)
{
availablePairs[oldLod][newLod]--;
//available[oldLod]--;

SystemTools::Log ("%i from %i to %i\n", i, newLod, oldLod);

newLod = oldLod;
}
}

data[i] = (oldLod<<4) | newLod;
}

if (1) // proof
{
SystemTools::Log ("\nResult:\n");

int oldCount[4] = {0,0,0,0};
int newCount[4] = {0,0,0,0};
int matchCount[4] = {0,0,0,0};

for (int i=0; i<count; i++)
{
int newLod = data[i] & 3;
int oldLod = (data[i]>>4) & 3;

SystemTools::Log ("%i: (o%i n%i)  m%i\n", i, oldLod, newLod, oldLod==newLod);

oldCount[oldLod]++;
newCount[newLod]++;
if (newLod==oldLod) matchCount[newLod]++;
}

SystemTools::Log ("\noldCount: %i %i %i %i\n", oldCount[0], oldCount[1], oldCount[2], oldCount[3]);
SystemTools::Log ("newCount: %i %i %i %i\n", newCount[0], newCount[1], newCount[2], newCount[3]); // this should match the previous values
SystemTools::Log ("matchCnt: %i %i %i %i\n\n", matchCount[0], matchCount[1], matchCount[2], matchCount[3]); // should be higher
}

}


TestMatching

Initial:
0: (o0 n0)  m1
1: (o1 n1)  m1
2: (o3 n2)  m0
3: (o1 n1)  m1
4: (o1 n2)  m0
5: (o0 n1)  m0
6: (o0 n1)  m0
7: (o1 n3)  m0
8: (o2 n3)  m0
9: (o1 n1)  m1
10: (o0 n3)  m0
11: (o1 n0)  m0
12: (o0 n1)  m0
13: (o3 n1)  m0
14: (o1 n0)  m0
15: (o1 n2)  m0
16: (o3 n2)  m0
17: (o2 n0)  m0
18: (o2 n2)  m1
19: (o0 n1)  m0
20: (o1 n3)  m0
21: (o2 n0)  m0
22: (o1 n1)  m1
23: (o3 n1)  m0
24: (o3 n1)  m0
25: (o0 n2)  m0
26: (o3 n1)  m0
27: (o0 n1)  m0
28: (o0 n3)  m0
29: (o2 n2)  m1
30: (o1 n3)  m0
31: (o0 n3)  m0

oldCount: 10 11 5 6
newCount: 5 13 7 7
matchCnt: 1 4 2 0

pairCount:      1 5 1 3  2 4 2 3  2 0 2 1  0 4 2 0

availablePairs: 1 2 1 0  2 4 0 3  1 0 2 1  0 3 1 0

2 from 2 to 3
5 from 1 to 0
6 from 1 to 0
7 from 3 to 1
8 from 3 to 2
11 from 0 to 1
13 from 1 to 3
14 from 0 to 1
17 from 0 to 2
20 from 3 to 1
23 from 1 to 3
24 from 1 to 3
25 from 2 to 0
30 from 3 to 1

Result:
0: (o0 n0)  m1
1: (o1 n1)  m1
2: (o3 n3)  m1
3: (o1 n1)  m1
4: (o1 n2)  m0
5: (o0 n0)  m1
6: (o0 n0)  m1
7: (o1 n1)  m1
8: (o2 n2)  m1
9: (o1 n1)  m1
10: (o0 n3)  m0
11: (o1 n1)  m1
12: (o0 n1)  m0
13: (o3 n3)  m1
14: (o1 n1)  m1
15: (o1 n2)  m0
16: (o3 n2)  m0
17: (o2 n2)  m1
18: (o2 n2)  m1
19: (o0 n1)  m0
20: (o1 n1)  m1
21: (o2 n0)  m0
22: (o1 n1)  m1
23: (o3 n3)  m1
24: (o3 n3)  m1
25: (o0 n0)  m1
26: (o3 n1)  m0
27: (o0 n1)  m0
28: (o0 n3)  m0
29: (o2 n2)  m1
30: (o1 n1)  m1
31: (o0 n3)  m0

oldCount: 10 11 5 6
newCount: 5 13 7 7
matchCnt: 4 9 4 4


• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 14
• 45
• 22
• 27
• ### Forum Statistics

• Total Topics
634044
• Total Posts
3015213
×