0

I am fairly new to C++, and am struggling through a problem that seems to have a solid solution but I just can't seem to find it. I have a contiguous array of ints starting at zero:

int i[6] = { 0, 1, 2, 3, 4, 5 }; // this is actually from an iterator

I would like to partition the array into groups of three. The design is to have two methods, j and k, such that given an i they will return the other two elements from the same group of three. For example:


i       j(i)    k(i)  
0       1       2  
1       0       2  
2       0       1  
3       4       5  
4       3       5  
5       3       4

The solution seems to involve summing the i with its value mod three and either plus or minus one, but I can't quite seem to work out the logic.

Improve this question
5
  • @OliCharlesworth: Because I don't clearly see the solution, I have just been experimenting with functions trying to stumble on something close; things like (i+1) % 3; Commented Mar 5, 2013 at 21:03
  • Do you mean groups of three as opposed to thirds (eg groups of two for a 6 long array)? Commented Mar 5, 2013 at 21:06
  • Further, how specific are these methods meant to be. For example, do they need to handle arrays of non-contiguous numbers. What should they do given the first 12 non-negative numbers? The i + 1 % 3 will work for j for the first half of the set, but you need to be able to detect when you are in the second half, which is dependent on the size of the partitions. Commented Mar 5, 2013 at 21:12
  • This looks like a case you can make a simple function and a switch statement. Commented Mar 5, 2013 at 21:19
  • @T.Kiley yes I mean groups of three. Commented Mar 5, 2013 at 21:23

4 Answers 4

Reset to default
1

This should work:

int d = i % 3;
int j = i - d + ( d == 0 );
int k = i - d + 2 - ( d == 2 );

or following statement for k could be more readable:

int k = i - d + ( d == 2 ? 1 : 2 );
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

This should do it:

int j(int i)
{
  int div = i / 3;
  if (i%3 != 0)
    return 3*div;
  else
    return 3*div+1;
}

int k(int i)
{
  int div = i / 3;
  if (i%3 != 2)
    return 3*div+2;
  else
    return 3*div+1;
}

Test.

If you want shorter functions:

int j(int i)
{
  return i/3*3 + (i%3 ? 0 : 1);
}

int k(int i)
{
  return i/3*3 + (i%3-2 ? 2 : 1);
}
Improve this answer

3 Comments

Brilliant! This makes perfect sense. Thank you!
Mine is more effective (no multiplication involved) :)
You almost deserve to be downvoted for that remark. Careful there ;)
0

Well, first, notice that

j(i) == j(3+i) == j(6+i) == j(9+i) == ...
k(i) == k(3+i) == k(6+i) == k(9+i) == ...

In other words, you only need to find a formula for

j(i), i = 0, 1, 2
k(i), i = 0, 1, 2

and then for the rest of the cases simply plug in i mod 3.

From there, you'll have trouble finding a simple formula because your "rotation" isn't standard. Instead of

i       j(i)    k(i)
0       1       2
1       2       0
2       0       1

for which the formula would have been

j(i) = (i + 1) % 3
k(i) = (i + 2) % 3

you have

i       j(i)    k(i)
0       1       2
1       0       1
2       0       2

for which the only formula I can think of at the moment is

j(i) = (i == 0 ? 1 : 0)
k(i) = (i == 1 ? 1 : 2)
Improve this answer

2 Comments

I think the elements of the array, are not guaranteed to be successive.
Ah, actually, I was referring to indices in the array, but in an unclear and ambiguous way. I should have written and referred to i(0), i(1), and i(2), instead of writing 0, 1, and 2. I was more focused on the idea for the formula than the presentation. Thanks for pointing out the need for clarification, though.
0

If the values of your array (let's call it arr, not i in order to avoid confusion with the index i) do not coincide with their respective index, you have to perform a reverse lookup to figure out their index first. I propose using an std::map<int,size_t> or an std::unordered_map<int,size_t>.

That structure reflects the inverse of arr and you can extra the index for a particular value with its subscript operator or the at member function. From then, you can operate purely on the indices, and use modulo (%) to access the previous and the next element as suggested in the other answers.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.