Jump to content
  • Advertisement
Sign in to follow this  
JoeJ

Some kind of sorting matching pairs problem

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!