Need help

[Dani90]

Hello..i have a set of different correct integers and i want to form a series from this numbers so that the difference between two consecutive numbers in this series is one or minus one

so i want to write a backtracking algorithm to find all possible solution to this issue

for example i have the following numbers: 1 , 2 , 2 , 1 , 3 , 4 , 4 , 5 , 5 , 6
it becomes : 1 , 2 , 1 , 2 , 3 , 4 , 5 , 4 , 5 , 6
or becomes: 1 , 2 , 1 , 2 , 3 , 4 , 5 , 6 , 5 , 4
and this set of numbers has no solution :1 , 1 , 2 , 2 , 3 , 4 , 4 , 5 , 5 , 7

[jonnin]

why do you need backtracking? This can be solved with iteration, I think, from the very first number.
1, you can have 2 or 0.
1 and 2, you can have 1 and 3
1 and 0 you can have 1 and -1

basically, each number spawns 2 possible next numbers. This suggests a binary tree to grow the sequence and traversals to spew out the results (I suppose the traversals are a form of backtracking, if you want to think of it that way??).

Does that make sense? Or am I thinking about it wrong?

[icy1]

Is there a more elegant way to find an element's index than std::distance<nasty iterator type>(it1, it2) ?
Edit: nevermind, found it -- can just subtract iterators. Removed sort since I really wanted to find the minimum element once before starting the recursion. Made more consistent.
Edit2: I should note that I arbitrarily chose to start with minimum element. One could also start with the maximum element, in which case there'd be at least one more solution.
Edit3: Updated to also find solutions starting with maximum element.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Attempt finding a sequence from an array of numbers so that 
//   consecutive numbers only differ by 1.  Example:
//   [ 1, 2, 2, 1, 3, 4, 4, 5, 5, 6 ]
// One possible solution would be 
//   [ 1, 2, 1, 2, 3, 4, 5, 4, 5, 6 ]

void Show(const vector<int>& v)
{
    for (auto& n : v)
        cout << n << " ";
    cout << endl;
}

// i - index of next spot to fill, from 1 to v.size()-1
void DifferOne(vector<int> v, int i)
{
    if (i == v.size())
    {
        Show(v);
        return;
    }

    // From remainder of array, find element one lower than previous value
    auto it = find(v.begin()+i, v.end(), v[i-1] - 1);
    if (it != v.end())
    {
        vector<int> dup(v);
        swap(dup[i], dup[it - v.begin()]);
        DifferOne(dup, i+1);
    }
    
    // From remainder of array, find element one higher than previous value
    it = find(v.begin()+i, v.end(), v[i-1] + 1);
    if (it != v.end())
    {
        vector<int> dup(v);
        swap(dup[i], dup[it - v.begin()]);
        DifferOne(dup, i+1);
    }
}

void DifferOneFind(const vector<int>& orig)
{
    vector<int> v(orig);
    auto it = min_element(v.begin(), v.end());
    swap(v[0], v[it-v.begin()]);
    DifferOne(v, 1);

    vector<int> v2(orig);
    it = max_element(v2.begin(), v2.end());
    swap(v2[0], v2[it-v2.begin()]);
    DifferOne(v2, 1);
}

int main() 
{
    vector<int> v { 1, 2, 2, 1, 3, 4, 4, 5, 5, 6 };
    cout << "Input:\n";
    Show(v);

    cout << "\nOutput:\n";
    DifferOneFind(v);

    return 0;
}

running at https://repl.it/@icy_1/SympatheticEasygoingSyntax

Input:
1 2 2 1 3 4 4 5 5 6 

Output:
1 2 1 2 3 4 5 4 5 6 
1 2 1 2 3 4 5 6 5 4 
6 5 4 5 4 3 2 1 2 1 

[icy1]

Just realized that the answer doesn't necessarily need to start with the min or the max =/

Things get more complex if you find an answer where the first and last happen to differ by one -- this means there are automatically v.size()-1 more solutions from circular rotation.

To illustrate, if input is
1 2 2 3

One solution:
1 2 3 2

Since first(1) and last(2) differ by one, we have three more solutions from rotation:
2 3 2 1
3 2 1 2
2 1 2 3