CODEWITHSUNDEEP
c++algorithmpairing
Bercovici Adrian
Bercovici Adrian

Reputation: 9370

General formula for pairing members of array?

Hello guys I am having the following problem:

I have an array with a lenght that is a multiple of 4 e.g:

{1,2,3,4,5,6,7,8}

I want to know how can i get the numbers in the following pairs: {1,4},{2,3},{5,8},{6,7}.....(etc)

Suppose i loop through them and i want to get the index of the pair member from my current index

int myarr[8]={1,2,3,4,5,6,7,8};

for(int i=0;i<8;i++)
**j= func(i)**

I have thought of something like this:

f(1)=4
f(4)=1
and i would be taking: **f(i)=a * i + b**
(i think a linear function is enough)
It would result: f(i)=j=-i+5 .
How can i generalise this for more then 4 members? What do you do in cases where you need a general formula for pairing elements?

Upvotes: 2

Views: 179

Answers (3)

arekolek
arekolek

Reputation: 9621

About the generalization, this should do it:

auto pairs(const vector<int>& in, int groupLength = 4) {
    vector<pair<int, int>> result;
    int groups = in.size() / groupLength;
    for (int group = 0; group < groups; ++group) {
        int i = group * groupLength;
        int j = i + groupLength - 1;
        while (i < j) {
            result.emplace_back(in[i++], in[j--]);
        }
    }
    return result;
}

You can run this code online.

If you are just looking for a formula to calculate the indices, then in general case it's:

int f(int i, int k = 4) {
    return i + k - 2 * (i % k) - 1;
}

Turns out your special case (size 4) is sequence A004444 in OEIS.

In general you have "nimsum n + (size-1)".

Upvotes: 1

Codor
Codor

Reputation: 17605

You could do it as follows by keeping the incremental iteration but use a function depending on the current block and the remainder as follows.

int myarr[8]={1,2,3,4,5,6,7,8};

int Successor(int i)
{
    int BlockStart = i / 4;
    int Remainder = i % 4;
    int j = 0;
    if ( Remainder == 0 )
        j = 0;
    else if ( Remainder == 1 )
        j = 3;
    else if ( Remainder == 2 )
        j = 1;
    else if ( Remainder == 3 )
        j = 2
    return BlockStart + j;
}

for(int i = 0; i < 8; i++)
{
    j = f(i);
    // usage of the index
}

Upvotes: 1

Rajeev Singh
Rajeev Singh

Reputation: 3332

Basically, if i is odd j would be i+3, otherwise j = i+1;

int func(int i) {
    if(i%2 != 0)
        return i+3;
    else
        return i+1;
}

This will generate

func(1) = 4, func(2) = 3, func(5) = 8, func(6) = 7 // {1,4},{2,3},{5,8},{6,7}.

Upvotes: 2

Related Questions