Finding a lexicographically minimum permutation

[BBrandon]

I want to make a program that finds me the lexicographically minimum (basically where all of the numbers are not dupilcates and are integers above 0, and you want these numbers to be as close to the minimal counting numbers as possible. For example, [1,2,3,4] is more lexicographically minimum than [1,2,3,5] because the 4 is less than the 5.) permutation when you are given a permutation that contains the sum of every two numbers in the lexicographically minimum permutation. You're also given the N amount of numbers in the lexicographically minimum permutation.

Sample Input:
5
4 6 7 6

Sample Output:
3 1 5 2 4

the lexicographically minimum permutation produces the input permutation produces because 3+1=4, 1+5=6, 5+2=7, and 2+4=6.

[dutch]

Firstly, wouldn't [1,2,3,4,5] be the lexi-min-perm?

Secondly,

you are given a permutation that contains the sum of every two numbers in the lexicographically minimum permutation

But the sum of every two numbers of your solution are 3, 4, 5, 6, 5, 6, 7, 7, 8, 9 (if dups are allowed).

If there is a link to the problem, post it.

[BBrandon]

Farmer John is lining up his N cows (2≤N≤103), numbered 1…N, for a photoshoot. FJ initially planned for the i-th cow from the left to be the cow numbered ai, and wrote down the permutation a1,a2,…,aN on a sheet of paper. Unfortunately, that paper was recently stolen by Farmer Nhoj!
Luckily, it might still possible for FJ to recover the permutation that he originally wrote down. Before the sheet was stolen, Bessie recorded the sequence b1,b2,…,bN−1 that satisfies bi=ai+ai+1 for each 1≤i<N.

Based on Bessie's information, help FJ restore the "lexicographically minimum" permutation a that could have produced b. A permutation x is lexicographically smaller than a permutation y if for some j, xi=yi for all i<j and xj<yj (in other words, the two permutations are identical up to a certain point, at which x is smaller than y). It is guaranteed that at least one such a exists.

SCORING:
Test cases 2-4 satisfy N≤8.
Test cases 5-10 satisfy no additional constraints.
INPUT FORMAT (file photo.in):
The first line of input contains a single integer N.
The second line contains N−1 space-separated integers b1,b2,…,bN−1.

OUTPUT FORMAT (file photo.out):
A single line with N space-separated integers a1,a2,…,aN.
SAMPLE INPUT:
5
4 6 7 6
SAMPLE OUTPUT:
3 1 5 2 4
a produces b because 3+1=4, 1+5=6, 5+2=7, and 2+4=6.

It's from a USACO training camp of mine and I don't quite know how to solve it, so I'm trying to get some help on how to solve it and what the solution would be.

[dutch]

Oh, I see. So the sums are just for the consecutive pairs of values.

It seems a matter of trying out all the possibilities in the breakdown of the first sum (in order) and seeing if you can get a legal sequence with no duplicates.

E.g,

Suppose the goal sequence is:

 8  4  5  2  7  6  1  3

Then the given sums would be:

12  9  7  9 13  7  4

Trying to work it out by going through the breakdowns of the first sum in order:

12: (1 11)
 9:    can't work (11 >= 9)

12: (2 10)
 9:    can't work (11 >= 9)

12: (3  9)
 9:    can't work (11 >= 9)

12: (4  8)
 9:    (8  1)
 7:       (1  6)
 9:          (6  3)
13:             (3 10)
 7:                can't work (10 >= 7)

12: (5  7)
 9:    (7  2)
 7:       (2  5) can't work (5 is dup)

12: (7  5)
 9:    (5  4)
 7:       (4  3)
 9:          (3  6)
13:             (6  7) can't work (7 is dup)

12: (8  4)
 9:    (4  5)
 7:       (5  2)
 9:          (2  7)
13:             (7  6)
 7:                (6  1)
 4:                   (1  3)
 
And we get:

 8  4  5  2  7  6  1  3

[dutch]

I have a solution, but I won't post it unless you ask me to.

[lastchance]

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int BIG = 1000000000;

//======================================================================

void adjustForA1( vector<int> &a, int a1 )       // a[0] irrelevant; add a1 to odds, subtract a1 from evens
{
   for ( int &value : a )
   {
      value -= a1;
      a1 = -a1;
   }
}

//======================================================================

bool check( const vector<int> &a )               // Check that this is the numbers 1, ..., N (ignoring a[0])
{
   int N = a.size() - 1;
   set<int> S( a.begin() + 1, a.end() );
   return ( S.size() == N && ( *S.begin() == 1 ) && ( *S.rbegin() == N ) );
}

//======================================================================

int main()
{
// istream &in = cin;
// istringstream in( "5       \n"                   // Original example
//                   "4 6 7 6 \n" );
   istringstream in( "8                    \n"      // Dutch's example
                     "12  9  7  9 13  7  4 \n" );


   // Input data
   int N;
   in >> N;
   vector<int> a(1+N), b(1+N);         // ignore index [0]
   for ( int i = 1; i < N; i++ ) in >> b[i];


   // First set values as if a[1]=0. 
   // Later, adjust this: even indices - subtract a[1]; odd indices: add a[1];
   bool even = true;                   // Here, refers to i+1
   int minEven = BIG, minOdd = 0;      // a[1] is initially 0, hence setting of minOdd.
   for ( int i = 1; i < N; i++ )
   {
      a[i+1] = b[i] - a[i];
      if (  even && a[i+1] < minEven ) minEven = a[i+1];
      if ( !even && a[i+1] < minOdd  ) minOdd  = a[i+1];
      even = !even;
   }

   // Work out what a[1] would have to be if 1 is to be in the even or odd indices
   int a1Even = minEven - 1;
   int a1Odd  = 1 - minOdd;


   // Now try one or both of these two possible values for a[1]
   bool ok = true;
   if ( a1Odd < 1 )                    // Only one possible solution with 1 lying in even indices
   {
      adjustForA1( a, a1Even );
      ok = check( a );
   }
   else if ( a1Even < 1 )              // Only one possible solution with 1 lying in odd indices
   {
      adjustForA1( a, a1Odd );
      ok = check( a );
   }
   else                                // Two possible solutions: gonna have to try them
   {
      int a1 = min( a1Even, a1Odd );   // Try this first; if it works it's optimal (minimum lexico..whatever)
      adjustForA1( a, a1 );
      ok = check( a );
      if ( !ok )                       // Yuk; try the other
      {
         a1 = max( a1Even, a1Odd ) - a1;
         adjustForA1( a, a1 );
         ok = check( a );
      }
   }


   // Write out if solved; cry if not
   if ( !ok )                        
   {
      cout << "Something's wrong!";
      return 1;
   }
   else                                // Write solution
   {
      for ( int i = 1; i <= N; i++ ) cout << a[i] << ' ';
      cout << '\n';
   }
}

[BBrandon]

I have a solution, but I won't post it unless you ask me to.

I would like to see it as well!

[dutch]

Well, now I'm embarrassed after seeing lastchance's more efficient solution, but here it is.

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> input(n - 1), goal(n);
    for (int i = 0; i < n - 1; ++i) std::cin >> input[i];

    for (int i = 1; i <= n; ++i) {
        int a = input[0] - i;
        if (a < 1 || a > n || a == i) continue;

        goal[0] = i;
        goal[1] = a;

        std::vector<bool> used(n + 1);
        used[i] = used[a] = true;

        size_t j = 1;
        for ( ; j < input.size(); ++j) {
            int b = input[j] - a;
            if (b < 1 || b > n || used[b]) break;
            goal[j + 1] = b;
            used[b] = true;
            a = b;
        }

        if (j == input.size()) {
            for (int x: goal) std::cout << x << ' ';
            std::cout << '\n';
            break;
        }
    }
}

[dutch]

Playing around with the programs again, I seem to have stumbled upon an input that seems to work for mine but doesn't seem to work for lastchance's solution (it gives the "Something's wrong!" response). I don't see why, though.

Here's the input, which also has the answer on the 3rd line. Modified code follows that checks the answer.

100
11 84 77 76 93 74 99 57 30 105 149 127 147 179 126 86 101 124 139 89 113 147 99 88 125 104 43 37 50 117 189 157 98 88 153 146 143 174 124 111 100 120 158 84 89 175 158 149 106 110 115 53 54 74 127 93 32 71 146 96 25 44 43 68 100 82 41 13 71 110 46 78 161 119 44 63 101 90 77 123 143 141 128 89 56 73 126 151 176 162 79 13 32 63 130 191 169 139 108 
3 8 76 1 75 18 56 43 14 16 89 60 67 80 99 27 59 42 82 57 32 81 66 33 55 70 34 9 28 22 95 94 63 35 53 100 46 97 77 47 64 36 84 74 10 79 96 62 87 19 91 24 29 25 49 78 15 17 54 92 4 21 23 20 48 52 30 11 2 69 41 5 73 88 31 13 50 51 39 38 85 58 83 45 44 12 61 65 86 90 72 7 6 26 37 93 98 71 68 40 

lastchance's code:

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int BIG = 1000000000;

void adjustForA1( vector<int> &a, int a1 )
{
   for ( int &value : a )
   {
      value -= a1;
      a1 = -a1;
   }
}

bool check( const vector<int> &a )
{
   int N = a.size() - 1;
   set<int> S( a.begin() + 1, a.end() );
   return ( int(S.size()) == N && ( *S.begin() == 1 ) && ( *S.rbegin() == N ) );
}

int main()
{
   istream &in = cin;
   int N;
   in >> N;
   vector<int> a(1+N), b(1+N);
   for ( int i = 1; i < N; i++ ) in >> b[i];
   vector<int> answer(1+N);
   for ( int i = 1; i <= N; i++ ) in >> answer[i];
   
   bool even = true;
   int minEven = BIG, minOdd = 0;
   for ( int i = 1; i < N; i++ )
   {
      a[i+1] = b[i] - a[i];
      if ( i % 2 == 0)
      if (  even && a[i+1] < minEven ) minEven = a[i+1];
      if ( !even && a[i+1] < minOdd  ) minOdd  = a[i+1];
      even = !even;
   }

   int a1Even = minEven - 1;
   int a1Odd  = 1 - minOdd;

   bool ok = true;
   if ( a1Odd < 1 )
   {
      adjustForA1( a, a1Even );
      ok = check( a );
   }
   else if ( a1Even < 1 )
   {
      adjustForA1( a, a1Odd );
      ok = check( a );
   }
   else
   {
      int a1 = min( a1Even, a1Odd );
      adjustForA1( a, a1 );
      ok = check( a );
      if ( !ok )
      {
         a1 = max( a1Even, a1Odd ) - a1;
         adjustForA1( a, a1 );
         ok = check( a );
      }
   }

   if ( !ok )                        
   {
      cout << "Something's wrong!\n";
      return 1;
   }
   else
   {
//      for ( int i = 1; i <= N; i++ ) cout << a[i] << ' ';
//      cout << '\n';

      for ( int i = 1; i <= N; i++ )
         if ( a[i] != answer[i] ) {
            cout << "mismatch\n";
            return 1;
         }
      cout << "good\n";
   }
}

My code:

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> input(n - 1), answer(n), goal(n);
    for (int i = 0; i < n - 1; ++i) std::cin >> input[i];
    for (int i = 0; i < n;     ++i) std::cin >> answer[i];

    for (int i = 1; i <= n; ++i) {
        int a = input[0] - i;
        if (a < 1 || a > n || a == i) continue;

        goal[0] = i;
        goal[1] = a;

        std::vector<bool> used(n + 1);
        used[i] = used[a] = true;

        size_t j = 1;
        for ( ; j < input.size(); ++j) {
            int b = input[j] - a;
            if (b < 1 || b > n || used[b]) break;
            goal[j + 1] = b;
            used[b] = true;
            a = b;
        }

        if (j == input.size()) {
            //for (int x: goal) std::cout << x << ' ';
            //std::cout << '\n';
            for (int i = 0; i < n; ++i)
                if (goal[i] != answer[i]) {
                    std::cout << "mismatch\n";
                    return 1;
                }
            std::cout << "good\n";
            break;
        }
    }
}

And here's some code to generate random input (with the answer):

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

int main(int argc, char** argv) {
    size_t n = 1000;
    if (argc > 1) n = std::stoi(argv[1]);
    std::vector<int> a(n);
    std::iota(a.begin(), a.end(), 1);
    std::shuffle(a.begin(), a.end(),
        std::default_random_engine(std::random_device{}()));
    std::cout << a.size() << '\n';
    for (size_t i = 1; i < a.size(); ++i) std::cout << a[i] + a[i - 1] << ' ';
    std::cout << '\n';
    for (int n: a) std::cout << n << ' ';
    std::cout << '\n';
}

[BBrandon]

I figured out why it says something is wrong btw. lastchance's solution only wants to give an absolutely lexographicallly minimal solution. So if the numbers are not in perfect counting order, it won't print it. I easily fixed this by just deleting the

// Write out if solved; cry if not
if ( !ok )
{
cout << "Something's wrong!";
return 1;
}

Still, thanks for the solutions!

[lastchance]

Hi Dutch - my code (as in my original version) produced your intended answer when run - see below. I checked number by number and the outputs are identical.

EDIT - When you modified my code and put it in your last post you added a line 41
if ( i % 2 == 0)
which just crippled my code! I was dealing quite happily with even and odd with my even = !even; toggles.

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int BIG = 1000000000;

//======================================================================

void adjustForA1( vector<int> &a, int a1 )       // a[0] irrelevant; add a1 to odds, subtract a1 from evens
{
   for ( int &value : a )
   {
      value -= a1;
      a1 = -a1;
   }
}

//======================================================================

bool check( const vector<int> &a )               // Check that this is the numbers 1, ..., N (ignoring a[0])
{
   int N = a.size() - 1;
   set<int> S( a.begin() + 1, a.end() );
   return ( S.size() == N && ( *S.begin() == 1 ) && ( *S.rbegin() == N ) );
}

//======================================================================

int main()
{
// istream &in = cin;
// istringstream in( "5       \n"                   // Original example
//                   "4 6 7 6 \n" );
// istringstream in( "8                    \n"      // Dutch's example
//                   "12  9  7  9 13  7  4 \n" );
   istringstream in( "100 \n"
                     "11  84  77  76  93  74  99  57  30  105 149 127 147 179 126 86    "
                     "101 124 139 89  113 147 99  88  125 104  43  37  50 117 189    "
                     "157 98  88  153 146 143 174 124 111 100 120 158  84  89 175    "
                     "158 149 106 110 115 53  54  74  127  93  32  71 146  96  25 44 "
                     "43  68  100 82  41  13  71  110 46   78 161 119  44  63 101 90 77  "
                     "123 143 141 128 89  56  73  126 151 176 162  79  13  32  63 130 "
                     "191 169 139 108                                          \n" );

   // Input data
   int N;
   in >> N;
   vector<int> a(1+N), b(1+N);         // ignore index [0]
   for ( int i = 1; i < N; i++ ) in >> b[i];


   // First set values as if a[1]=0. 
   // Later, adjust this: even indices - subtract a[1]; odd indices: add a[1];
   bool even = true;                   // Here, refers to i+1
   int minEven = BIG, minOdd = 0;      // a[1] is initially 0, hence setting of minOdd.
   for ( int i = 1; i < N; i++ )
   {
      a[i+1] = b[i] - a[i];
      if (  even && a[i+1] < minEven ) minEven = a[i+1];
      if ( !even && a[i+1] < minOdd  ) minOdd  = a[i+1];
      even = !even;
   }

   // Work out what a[1] would have to be if 1 is to be in the even or odd indices
   int a1Even = minEven - 1;
   int a1Odd  = 1 - minOdd;


   // Now try one or both of these two possible values for a[1]
   bool ok = true;
   if ( a1Odd < 1 )                    // Only one possible solution with 1 lying in even indices
   {
      adjustForA1( a, a1Even );
      ok = check( a );
   }
   else if ( a1Even < 1 )              // Only one possible solution with 1 lying in odd indices
   {
      adjustForA1( a, a1Odd );
      ok = check( a );
   }
   else                                // Two possible solutions: gonna have to try them
   {
      int a1 = min( a1Even, a1Odd );   // Try this first; if it works it's optimal (minimum lexico..whatever)
      adjustForA1( a, a1 );
      ok = check( a );
      if ( !ok )                       // Yuk; try the other
      {
         a1 = max( a1Even, a1Odd ) - a1;
         adjustForA1( a, a1 );
         ok = check( a );
      }
   }


   // Write out if solved; cry if not
   if ( !ok )                        
   {
      cout << "Something's wrong!";
      return 1;
   }
   else                                // Write solution
   {
      for ( int i = 1; i <= N; i++ ) cout << a[i] << ' ';
      cout << '\n';
   }
}

3 8 76 1 75 18 56 43 14 16 89 60 67 80 99 27 59 42 82 57 32 81 66 33 55 70 34 9 28 22 95 94 63 35 53 100 46 97 77 47 64 36 84 74 10 79 96 62 87 19 91 24 29 25 49 78 15 17 54 92 4 21 23 20 48 52 30 11 2 69 41 5 73 88 31 13 50 51 39 38 85 58 83 45 44 12 61 65 86 90 72 7 6 26 37 93 98 71 68 40 

[dutch]

I'm braindead. Look at line 41 in my modification of your code above! I was playing around with it and left that piece of garbage in (I rewrote it to get rid of even and then (only partly) reverted it). Sorry about that. It works just fine, of course. :)

[lastchance]

Hi Dutch - yes, I had just worked that out (see the edit to my last post).

It happens - but it didn't half give me a frantic Sunday night!

Thanks for playing with the code; it was a fun problem.

[BBrandon]

Ty for the solutions for this problem! I've also got a few more problems I need help with and it would be nice if you guys could try them out.
http://www.cplusplus.com/forum/general/267389/

[againtry]

Bit late to the party but a bit of ecclesiastical fatuosity and sugary fun is never too far away ;)

#include <iostream>

void display_array( int* array, size_t in_size);
void check_right( int* in, int* out, size_t in_size, size_t idx_max);
void check_left( int* in, int* out, size_t idx_max);
void check_valid( int* out, size_t out_size);

void complete_check
( int* in, int* out, size_t idx_max, size_t out_size, size_t fst, size_t snd );

int main()
{
    int input[]
    {
        11,84,77,76,93,74,99,57,30,105,149,127,147,179,126,86,101,124,139,89,
        113,147,99,88,125,104,43,37,50,117,189,157,98,88,153,146,143,174,124,
        111,100,120,158,84,89,175,158,149,106,110,115,53,54,74,127,93,32,71,146,
        96,25,44,43,68,100,82,41,13,71,110,46,78,161,119,44,63,101,90,77,123,
        143,141,128,89,56,73,126,151,176,162,79,13,32,63,130,191,169,139,108
    };
    
    /*
    {
        3,8,76,1,75,18,56,43,14,16,89,60,67,80,99,27,59,42,82,57,32,81,66,
        33,55,70,34,9,28,22,95,94,63,35,53,100,46,97,77,47,64,36,84,74,10,79,96,
        62,87,19,91,24,29,25,49,78,15,17,54,92,4,21,23,20,48,52,30,11,2,69,41,
        5,73,88,31,13,50,51,39,38,85,58,83,45,44,12,61,65,86,90,72,7,6,26,37,
        93,98,71,68,40
    };
    */
    
    //{12,9,7,9,13,7,4};// 8,4,5,2,7,6,1,3
    //{17,12,9,7,9,13,7,4};// 9,8,4,5,2,7,6,1,3
    //{4,5,6,10,11}; // 1,3,2,4,6,5
    //{11,10,6,5,4}; // 5,6,4,2,3,1
    //{11,9,7,5,3}; // 6,5,4,3,2,1 AND 5,6,3,4,1,2
    //{13,11,9,7,5,3}; // 7,6,5,4,3,2,1
    //{4,5,6,10,11}; // 1,3,2,4,6,5
    //{4,6,7,6}; // 3,1,5,2,4
    //{17,12,9,7,9,13,7,4}; // 9,8,4,5,2,7,6,1,3
    //{3,5,7,9,11,13,15,17,19}; // 1,2,3,4,5,6,7,8,9,10 AND 2,1,4,3,6,5,8,7,10,9
    //{3,5,7,9,11,13,15,17,19,21}; // 1,2,3,4,5,6,7,8,9,10,11
    //{3,5,7,9,11,13,15,17,19,21,23};
    // 1,2,3,4,5,6,7,8,9,10,11,12 AND 2,1,4,3,6,5,8,7,10,9,12,11
    
    size_t input_size = sizeof(input)/sizeof(int);
    
    size_t output_size = input_size + 1;
    
    int* output = new int[output_size]{0};
    int* check = new int[output_size]{0};
    
    display_array(input, input_size);
    std::cout << "INPUT\n\n";
    
    // FIND INDEX OF largest NUMBER
    size_t largest{0};
    
    for(size_t i = 0; i < input_size; i++)
    {
        if(input[i] > input[largest])
            largest = i;
    }
    
    // first + second = input[largest]
    int first = 0;
    int second = 0;
    
    // FIND ALL POSSIBLE VALUE PAIRS THAT ADD UP TO input[largest]
    for (size_t i = 1; i < output_size + 1; i++)
    {
        for(size_t j = 1; j <  output_size + 1; j++)
        {
            if( (i + j) == input[largest] )
            {
                first = i;
                second = j;
                
                // FIND VALID OUTPUT ARRAY(S) FOR EACH PAIR
                complete_check( input, output, largest, output_size, first, second );
            }
        }
    }
    
    delete[] output;
    output = nullptr;
    
    delete[] check;
    output = nullptr;
    
    return 0;
}

void display_array( int* array, size_t size)
{
    for(int i = 0; i < size; i++)
    {
        std::cout << array[i];
        if(i < size - 1 )
            std::cout << ',';
    }
    std::cout << '\n';
}

void check_right(int* in, int* out, size_t in_size, size_t idx_max)
{
    for(size_t i = 1; i < in_size - 1 ; i++ )
        out[idx_max + i + 1] = in[idx_max + i] - out[idx_max + i];
}

void check_left(int* in, int* out, size_t idx_max)
{
    for(int i = idx_max; i > 0; i-- )
        out[i- 1] = in[i-1] - out[i];
}

void check_valid(int* out, size_t out_size)
{
    int* check = new int[out_size]{0};
    
    for(size_t i = 0; i < out_size; i++)
        check[i] = 0;
    
    for(size_t i = 0; i < out_size; i++)
        check[out[i] - 1]++;
    
    bool valid = true;
    for(size_t i = 0; i < out_size; i++)
    {
        if (check[i] != 1)
        {
            valid = false;
            break;
        }
    }
    
    if(valid == true)
    {
        display_array(out, out_size);
        std::cout << "VALID\n\n";
    }
    
    return;
}

void complete_check
( int* in, int* out, size_t idx_max, size_t out_size, size_t fst, size_t snd )
{
    out[idx_max] = fst;
    out[idx_max + 1] = snd;
    
    check_right(in, out, out_size, idx_max);
    check_left(in, out, idx_max);
    check_valid(out, out_size);
    
    return;
}

[dutch]

@againtry,
"check" is unused in main.
Lines 108 and 125 will write outside of the arrays.
And there is always only one answer since it's asking for the "lexicographically minimum" one.

[againtry]

Yeah, I had a sh!t-load of memory problems which I've solved but not posted.

Line 125 was in fact one of that load because I had forgotten that some of the spurious/invalid solutions can be have -ve elements.

I re-wrote the check function and deleted all the (desperation) delete's etc.

You got me on the "lexicographically minimum" business too, even though I realised the problem constraint was there. I'm making excuses but my initial line 72 where I wrote: for(size_t j = i + 1; j < output_size + 1; j++)

Thks for the comments. I think there's a slight/marginal difference in our two approaches (ie splitting or not splitting the array) but I'm impressed with the speed of you coming up with a solution.