Reorder array without duplication

I'm trying to find a way of allowing a user to re-order an array of integers without duplication of values.
If the array is of size n, the values will range from 1 to n and each value can only appear once. (At the moment n=4, but that is likely to increase)
So 1,2,3,4 and 4,2,1,3 are valid but 1,2,3,1 and 1,4,4,2 are not.

When the user presses button_x, array[x] increases by 1. If the result exists later in the array, the later values need to be adjusted accordingly, without being greater than n.

For example, changing array[2] from Start to New, the array would end up as Adjusted.

Start         New           Adjusted
1,2,3,4       1,3,3,4       1,3,4,2

The closest I've go so far is this.

const int max = 4;
int array[max] = {1,2,3,4};

for (int i=0; i < max; i++)
{
  for (int j=i+1; j < max; j++)
  {
    if (array[i] == array[j]) 
    {
      array[j]++;
      if (array[j] > max) array[j] = 1; 
    }
  }
}

This seems to work fine for a lot of situations, but certain combinations still result in duplicaiton.
Initially I thought the problem was if a change resulted in a duplicate at consecutive indexes, but the last sequence {3,4,1,2}, disproved that.

Start            New            Adjusted
1,2,3,4          1,3,3,4        1,3,4,1
1,2,3,4          1,2,4,4        1,2,4,1
4,2,3,1          4,3,3,1        4,3,4,1
4,3,2,1          4,3,3,1        4,3,4,1
4,1,3,2          4,1,3,3        4,1,3,4
4,1,2,3          4,2,2,3        4,2,3,4
3,4,1,2          4,4,1,2        4,1,2,3     << disproves my theory

You are looking for permutations of your array.

Have a look at - GitHub - RobTillaart/statHelpers: Arduino library with a number of statistic helper functions. · GitHub

There are some permutation related functions / examples that do what you want.

Check the perm1.ino example

If the digits in each array slot are in the range of 1 to n where n is the array size (1 to 4 in your example) then create a second array the same size of bools. init them all off. loop over your array and turn on the corresponding bool to the digit in the main array. At the end all of the bools should be 1.

Why not 1,3,2,4 ? Or would that also be acceptable?

But that breaks the rule because 1 appears twice.

If I understand that, I think that only detects whether there is duplication, but doesn't change any values in the integer array.

In principal that would be ok too.
I would expect a user, who doesn't know what’s going on under the hood, would have a slightly better chance of seeing what's going on if the result was 1,3,4,2 (or seemed more intuitive to me with other sequences).

Yeah. That's the problem.
1,3,4,2 is what I want to achieve
1,3,4,1 is what my code produces.

The easy way is to make an array of sorted indexes. This is how it's done on PC's and especially what to do on SD. It lets you sort the data different ways with different arrays and keep them all.

Search on linked lists. Sort indexes, not data.

Maybe...

const int max = 4;
int array[max] = {1,2,3,4};

int button = 1; // the digit position the user wants to increase, in this case from value 2 to value 3

int result = array[button] + 1;

if (result > 4) result = 1;

for (int i=0; i < max; i++) {
  if (array[i] == result) {
    array[i] = array[button];
    array[button] = result;
  }
}

However, you did specify

My solution above works the same if the result is earlier or later in the array.

What did you want to happen if the result exists earlier in the array?

Yes, that is what was asked for, no duplication. It's obvious how to order them; use the sort function.

I re-read the entire thread and did not see where you told us how DUPLICATES go into the array. What is the purpose of the array that allows duplicates?

Your examples all seem to have duplicates. What am I missing?

[edit] I think I understand... your example...

The homework assignment is to read (n) buttons in the array [0, 1, 2... n].
When button (x) is pressed, element (x) of the array is "reserved/removed", and elements (x+1) to (n) are placed in the next lower element order (not "increases" as you state).

So... you have two choices:
(1) Swap the "button press" with the next element...

Pin array   : [2, 3, 4, 5, 6, 7, 8, 9] 
Array size  : 8
the_array   : 01234567
Button press: 5 (pin 7)
New array   : 01234657

(2) Remove button press, shift elements "left" one, and place button press in last element.

Pin array   : [2, 3, 4, 5, 6, 7, 8, 9] 
Array size  : 8
the_array   : 01234567
Button press: 3 (pin 5)
New array   : 01245673

Code for both:

int button[] = { 2, 3, 4, 5, 6, 7, 8, 9 };  // button array size determines element array size
const int arraysize = sizeof(button) / sizeof(button[0]);
int the_array[arraysize];  // must not be read-only (not const)
int buttonpress, temporary;

void setup() {
  Serial.begin(115200);
  randomSeed(analogRead(A0));

  fence();
  Serial.print(F("Pin array   : ["));  // open the array
  for (int i = 0; i < arraysize; i++) {
    pinMode(button[i], INPUT_PULLUP);  // configure button pin direction
    Serial.print(button[i]);           // show the pin number
    if (i != arraysize - 1)            // housekeeping...
      Serial.print(F(", "));           // ... no final comma
  }
  Serial.println(F("] "));  // close the array

  Serial.print(F("Array size  : "));
  Serial.println(arraysize);
  Serial.print(F("the_array   : "));
  for (int i = 0; i < arraysize; i++) {
    Serial.print(i);   // show the index
    the_array[i] = i;  // populate the array
  }
  Serial.println();

  buttonpress = random(arraysize);  // chose a random button
  Serial.print(F("Button press: "));
  Serial.print(buttonpress);
  Serial.print(F(" (pin "));
  Serial.print(button[buttonpress]);
  Serial.print(F(")"));
  Serial.println();

  // ============================================= The Algorithms
  // move button press to end
  for (int i = buttonpress; i < arraysize; i++)  // start at button number
    the_array[i] = the_array[i + 1];             // shift elements down one
  the_array[arraysize - 1] = buttonpress;        // move button pressed end of array

  // swap button press with next element
  // the_array[buttonpress] = the_array[buttonpress + 1];
  // the_array[buttonpress + 1] = buttonpress;
  // ============================================= The Algorithms

  Serial.print(F("New array   : "));
  for (int i = 0; i < arraysize; i++)
    Serial.print(the_array[i]);
  Serial.println();
}

void loop() {
}

void fence() {
  for (byte i = 0; i < 50; i++)
    Serial.print("=");
  Serial.println();
}

What happens when it's already the max value N? Does it roll back to 1?

Initially, with rollover, the result always exists somewhere else in the array. But there's no adjustment made if the dupe only appears "earlier"; only adjust if it is "later"?

Since this is an Arduino forum, it would help to be consistent using zero-based indexes: array[2] is the third element.

Since 1,3,2,4 is also valid, and incrementing always creates a dupe somewhere, one easy approach is to swap with where the "new" value used to be. There is no loop or sorting. You have two arrays: one with the location of the corresponding value -- where is the 1, where is the 2, etc -- and the other array which you already have, what's in the first slot, what's the in second slot, etc.

With 1,2,3,4 when you increment the second slot

  1. What's the second slot? 2
  2. It's going to become: 3
  3. Where is the 3: third slot
  4. Put the 2 in the third slot
    • update "where is 2"
  5. Increment the second slot to 3 as originally planned
    • update "where is 3"

If you find it easier, you can always make either array (or both) one bigger than necessary and use base-1 indexing; leave element zero unused.

Just thinking out loud,

If you do not want duplicates, why not swap 2 elements on a button press?

With 3 buttons you can swap any pair in one to three presses.

With 4/5 buttons => one or two steps.

With 6 buttons => one step

My apologies. I'm finding it as challenging to articulate what I need as I am to code it. I'll try again.

(I think this is what my kid† describes as "rubber ducking": when you have a problem, explaining it to a rubber duck helps you clarify what you want to achieve. I think describing the following has helped me get my head around the problem and I MIGHT be closer to my own solution, but I'll leave it here anyway.)

1  4   5   8   3   7   6   2
       ^                             // change(5)
                                     // 5 + 1 = 6
                                     // 6 isn't earlier so 5 and 6 can be swapped
1   4   6   8   3   7   5   2
            ^                        // change(8)
                                     // 8 + 1 > max, so change(8) = 1
                                     // 1 is earlier, so change(8) = 2
                                     // 2 isn't earlier so 8 and 2 can be swapped
1   4   6   2   3   7   5   8
                ^                    // change(3)
                                     // 3 + 1 = 4
                                     // 4 is earlier, so change(3) = 5
                                     // 5 isn't earlier, so 3 and 5 are swapped
1   4   6   2   5   7   3   8
                            ^        // change(8)
                                     // 8 is the last value in the array so can be swapped
                                     // 8 + 1 > max, so change(8) = 1
                                     // 8 and 1 can be swapped
8   4   6   2   5   7   3   1
                            ^        // change(1)
                                     // 1 is the last value in the array so can be swapped
                                     // 1+1 = 2
                                     // 1 and 2 are swapped
8   4   6   1   5   7   3   2
            ^                        // change(1)
                                     // 1+1 = 2
                                     // 2 isn't earlier so 1 and 2 are swapped
8   4   6   2   5   7   3   1

† @xfpd My kid is at university - this is not someone's "homework assignment". I'm old enough to be a great-grandfather.

so all you need to do is swap that value at the current position with another value that is greater. But start looking for other values at the 1st position if the current position is the last position.

does this demonstrate what you want?

the array is printed and a '^' identifies the current position

?
  c - change val
  d - display
  n - next position
  r - reset
  q - quit

 1 2 3 4 5
 ^
n
 1 2 3 4 5
   ^
c
 1 3 2 4 5
   ^
c
 1 4 2 3 5
   ^
c
 1 5 2 3 4
   ^
c
 5 1 2 3 4
   ^
n
 5 1 2 3 4
     ^
n
 5 1 2 3 4
       ^
n
 5 1 2 3 4
         ^
c
 4 1 2 3 5
         ^
// 

#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>

unsigned int debug = 0;

const int N = 5;
unsigned  arr [N];
unsigned  pos;

// --------------------------------------------------------------------
void disp ()
{
    for (int n = 0; n < N; n++)
        printf (" %d", arr [n]);
    printf ("\n");

    for (unsigned n = 0; n < N; n++)
        printf (" %c", pos == n ? '^' : ' ');
    printf ("\n");
}

// --------------------------------------------------------------------
void swap (
    int a,
    int b )
{
    unsigned tmp;

    tmp     = arr [a];
    arr [a] = arr [b];
    arr [b] = tmp;
}

// --------------------------------------------------------------------
void change ()
{
    if (N == arr [pos])  {
        for (int n = 0; n < N; n++)
            if (1 == arr [n])  {
                swap (pos, n);
                break;
            }
    }

    else  {
        int n = 1 +pos;
        if (N == n)
            n = 0;

        for ( ; n < N; n++)
            if (arr [pos] < arr [n])  {
                swap (pos, n);
                break;
            }
    }

    disp ();
}

// --------------------------------------------------------------------
void reset ()
{
    for (int n = 0; n < N; n++)
        arr [n] = n +1;
    disp ();
}

// --------------------------------------------------------------------
void help (void)  {
    printf ("  c - change val\n");
    printf ("  d - display\n");
    printf ("  n - next position\n");
    printf ("  r - reset\n");
    printf ("  q - quit\n");
}

// --------------------------------------------------------------------
int main ()
{
    int   c;

    reset ();

    while ('q' != (c = getchar()))  {
        switch (c)  {
        case 'c':
            change ();
            break;

        case 'd':
            disp ();
            break;

        case 'n':
            if (N <= ++pos)
                pos = 0;
            disp ();
            break;

        case 'q':
            exit (0);
            break;

        case 'r':
            reset ();
            break;

        case '?':
            help ();
            break;

        case '\n':
            break;

        default:
            printf ("Error: %c unknown\n", c);
            help();
            break;
        };

    }

    return 0;
}

what should happen if there are no values in subsequent positions > the value at the current position? should it start at the first position?