C++

Forum

 
random number and swap

yat89 (81)
Hi all. I'm c++ beginner. I had write codes to generate two random numbers then swap those, but I can't get the correct solution. I don't know where I had done wrong because no errors occurred. Maybe I coded it wrong. Hopefully someone can help me. Any advice greatly appreciated.

There are conditions to generate random number.
i. Random Number 1 (r1) can't same with random number 2 (r2).
ii. Each number have their own open and close time. So, r1 and r2 must have same open and close time. For example, open time r1 is 7, then open time for r2 also must be 7.

The data as follows:
1 2 3 4 5 6 7 8 9 10 11 12
11 9 7 5 3 12 10 8 6 4 2 1
12 6 5 4 7 8 9 3 2 1 11 10

The time data: (column 2 is open time, column 3 is close time)
1 0 24
2 0 24
3 7 24
4 0 24
5 0 7
6 7 24
7 7 24
8 0 7
9 0 24
10 0 24
11 0 24
12 7 24

If further explanation is needed. Feel free to ask me. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.h>      // NULL 
#include <stdlib.h>     // srand
#include <time.h>       // time
#include <algorithm>    // swap
using namespace std;

// Declare functions
void input();
void swap_two_random_numbers();

// Declare variables 
const int rows_vect = 3;
const int cols_vect = 12;
const int rows_time = 12;
const int cols_time = 3;

vector<vector<int>> vect(rows_vect, vector <int>(cols_vect, 0));			
vector<vector<int>> time_data(rows_time, vector <int>(cols_vect, 0));	
vector<int> open(rows_time);
vector<int> close(rows_time);

int main()
{
	input();
	// Use current time as seed for random generator 
	srand(time(NULL));
	swap_two_random_numbers();
	return 0;
}

void input()
{
	// Open input files
	ifstream inpData("mydata.txt");								
	ifstream inpTime("time.txt");								
	
	// Assign mydata into array                    
	for (size_t i = 0; i < rows_vect; i++)
	{
		for (size_t j = 0; j < cols_vect; j++)
		{
			inpData >> vect[i][j];
			cout << vect[i][j] << "  ";
		}
		cout << endl;
	}
	cout << endl;

	// Assign time data into array
	for (size_t i = 0; i < rows_time; i++)
	{
		for (size_t j = 0; j < cols_time; j++)
		{
			inpTime >> time_data[i][j];
			cout << time_data[i][j] << "  ";
 		}
		cout << endl;
	}
	cout << endl;

	// Assign open time into array
	for (size_t i = 0; i < rows_time; i++)
	{
		open[i] = time_data[i][1];
	}

	// Assign close time into array
	for (size_t i = 0; i < rows_time; i++)
	{
		close[i] = time_data[i][2];
	}

	// Close input files
	inpData.close();
	inpTime.close();
}

void swap_two_random_numbers()
{
	for (size_t row = 0; row < vect.size(); row++)
	{
		// Generate two different random ints from col to col + 11, inclusive.
		int r1, r2;
		do
		{
			r1 = rand() % 12;
			r2 = rand() % 12;
		} 
		while ((r1 == r2) && (open[r1] != open[r2]) && (close[r1] != close[r2]));

		// Ensure r1 is less than r2; if not, swap them.
		if (r1 > r2)
		{
			int temp = r1;
			r1 = r2;
			r2 = temp;
		}

		cout << "For row " << row << ", positions "
			<< r1 << " and " << r2 << " were chosen.\n";

		swap(r1, r2);
	}
	cout << endl;

	// Displaying new solution after swapping r1 and r2
	for (size_t i = 0; i < rows_vect; i++)
	{
		for (size_t j = 0; j < cols_vect; j++)
		{
			cout << vect[i][j] << "  ";
		}
		cout << endl;
	}
	cout << endl;
}

JLBorges (13770)
Something like this, perhaps:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

struct item
{
    int unique_number ;
    int start_time ;
    int end_time ;

    // two items compare equal if they have the same start and end times
    friend bool operator== ( item a, item b )
    { return a.start_time == b.start_time && a.end_time == b.end_time ; }

    friend bool operator!= ( item a, item b ) { return !( a == b ) ; }

    friend std::ostream& operator<< ( std::ostream& stm, item it )
    { return stm << it.unique_number << ". (start:" << it.start_time << " end:" << it.end_time << ')' ; }
};

void random_swap( std::vector<item>& items )
{
    static std::mt19937 rng( std::random_device{}() ) ;

    // pick the first item position at random
    const std::size_t pos_a = std::uniform_int_distribution<std::size_t>( 0, items.size()-1 )(rng) ;

    // pick a random second item with the same start and end times
    // create a list of candidate positions
    std::vector<std::size_t> candidate_positions ;
    for( std::size_t i = 0 ; i < items.size() ; ++i )
        if( i != pos_a && items[pos_a] == items[i] ) candidate_positions.push_back(i) ;

    if( !candidate_positions.empty() ) // if the list is not empty
    {
        // pick a different random second item position from the list of candidates
        const std::size_t pos_cp = std::uniform_int_distribution<std::size_t>( 0, candidate_positions.size()-1 )(rng) ;
        const std::size_t pos_b = candidate_positions[pos_cp] ;

        // swap them
        #ifndef NDEBUG
        std::cout << "swap item " << items[pos_a] << " at position " << pos_a
                  << "\nwith item " << items[pos_b] << " at position " << pos_b << "\n\n" ;
        #endif // NDEBUG
        using std::swap ; swap( items[pos_a], items[pos_b] ) ;
    }
}

int main()
{
    std::vector<item> items
    {
        {  1,  0, 24 },
        {  2,  0, 24 },
        {  3,  7, 24 },
        {  4,  0, 24 },
        {  5,  0,  7 },
        {  6,  7, 24 },
        {  7,  7, 24 },
        {  8,  0,  7 },
        {  9,  0, 24 },
        { 10, 0, 24 },
        { 11, 0, 24 },
        { 12, 7, 24 }
    };

    for( int i = 0 ; i < 10 ; ++i ) random_swap(items) ;

    for( const item& it : items ) std::cout << it << '\n' ;
}

http://coliru.stacked-crooked.com/a/178726e9eb44ae2f
yat89 (81)
Hi JLBorges, sorry for troubling you. I think i made unclear explanation. Actually, what i want to do is:

First, generate two random number for each row of the following data/vector.
1 2 3 4 5 6 7 8 9 10 11 12
11 9 7 5 3 12 10 8 6 4 2 1
12 6 5 4 7 8 9 3 2 1 11 10

For example, for row 0. If first random number chosen is position 1 and second random number is position 10. Then I need to check either they share the same open and close time or not.

1 0 24
2 0 24
3 7 24
4 0 24
5 0 7
6 7 24
7 7 24
8 0 7
9 0 24
10 0 24
11 0 24
12 7 24

After checking, open and close time random number 1 and 2 are same which is 0 and 24, respectively. Then I need to swap those number. Then the solution for row 0 should be:

1 11 3 4 5 6 7 8 9 10 2 12

How can I do that? Since my codes above doesn't display the solution I want.

Sorry for troubling you.

JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>

struct item
{
    int unique_number ;
    int start_time ;
    int end_time ;

    // two items compare equal if they have the same start and end times
    friend bool operator== ( item a, item b )
    { return a.start_time == b.start_time && a.end_time == b.end_time ; }

    friend bool operator!= ( item a, item b ) { return !( a == b ) ; }

    friend std::ostream& operator<< ( std::ostream& stm, item it )
    { return stm << it.unique_number << ". (start:" << it.start_time << " end:" << it.end_time << ')' ; }
};

void random_swap( std::vector<item>& items )
{
    static std::mt19937 rng( std::random_device{}() ) ;

    // pick the first item position at random
    const std::size_t pos_a = std::uniform_int_distribution<std::size_t>( 0, items.size()-1 )(rng) ;

    // pick a different  second item position at random
    std::size_t pos_b = pos_a ;
    while( pos_b == pos_a ) pos_b = std::uniform_int_distribution<std::size_t>( 0, items.size()-1 )(rng) ;

    #ifndef NDEBUG
        std::cout << "\n first item " << items[pos_a] << " at position " << pos_a
                  << "\nsecond item " << items[pos_b] << " at position " << pos_b << '\n' ;
    #endif // NDEBUG

    if( items[pos_a] == items[pos_b] ) // if they share the same open and close times
    {
        // swap them
        #ifndef NDEBUG
            std::cout << "they share the same open and close times.\n**** swap them ****\n\n" ;
        #endif // NDEBUG

        using std::swap ; swap( items[pos_a], items[pos_b] ) ;
    }

    else // they share the same open and close times
    {
        // do nothing
        #ifndef NDEBUG
            std::cout << "do nothing\n" ;
        #endif // NDEBUG
    }
}

int main()
{
    std::vector<item> items
    {
        {  1,  0, 24 },
        {  2,  0, 24 },
        {  3,  7, 24 },
        {  4,  0, 24 },
        {  5,  0,  7 },
        {  6,  7, 24 },
        {  7,  7, 24 },
        {  8,  0,  7 },
        {  9,  0, 24 },
        { 10, 0, 24 },
        { 11, 0, 24 },
        { 12, 7, 24 }
    };
    for( const item& it : items ) std::cout << it.unique_number << ' ' ;

    const int N = 10 ;

    for( int i = 0 ; i < N ; ++i )
    {
        random_swap(items) ;
        for( const item& it : items ) std::cout << it.unique_number << ' ' ;
        std::cout << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/9d213f95a022bfe6
yat89 (81)
Hi JLBorges, thanks for your help. Since I'm still a beginner, your codes a bit tough for me to understand. But when go through with it. I got some idea how to improve my previous codes. which by using bool operator. I will try to write again the codes. I will come back again if i need to ask you something.

Btw, thanks again for your reply. Really appreciated.

Have a nice day!
yat89 (81)
I would like to ask. There are many terms / variables in the codes that I'm not familiar with it. It quite hard for me to understand it. Is there any other ways I could do to solve the problem.

Sorry for asking this. I'm still new to c++.
Actually what is
friend bool operator
? It is same as bool? Why can't we just use bool?

Also,
static std::mt19937 rng( std::random_device{}() ) ;
. It is same with srand(time(NULL))?

One more is 
1
2
3
 
#ifndef NDEBUG
            std::cout << "they share the same open and close times.\n**** swap them ****\n\n" ;
        #endif // NDEBUG

What is
#ifndef NDEBUG
?

I also would like to ask about my coded. Actually what i do wrong? Why can't display the result? Is there any ways I could improves my code to make it work?

Any advice really appreciated.
closed account (E0p9LyTq)
When you don't understand something there are resources that can help explain, you just have to search.

Two explanations of the friend declaration:
https://en.cppreference.com/w/cpp/language/friend

http://www.cplusplus.com/doc/tutorial/inheritance/

After you've searched (and hopefully found) an explanation and still unsure then do ask.

But please, make some effort to answer questions on your own first.

It is same with srand(time(NULL))?

Not the same. Another, and better, way to seed a random number generator. A C++ one.

The C library random number generator is IMO, to be polite, a mess. The C standard suggests not using srand/rand if there are other ways to generate random numbers.

A quick overview/tutorial on random number generation:
https://www.learncpp.com/cpp-tutorial/59-random-number-generation/
JLBorges (13770)
> Actually what is friend bool operator
> ? It is same as bool? Why can't we just use bool?

We can declare the function (overloaded operator) without the friend specifier;
but then we would have to define the function outside the class definition.

See: https://en.cppreference.com/w/cpp/language/friend


> static std::mt19937 rng( std::random_device{}() ) ;
> It is same with srand(time(NULL))?

No; it is different. The code uses the C++ random number library.
See: https://en.cppreference.com/w/cpp/numeric/random
More information: https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful


> What is #ifndef NDEBUG

The preprocessor supports conditional compilation of parts of the source file. The parts between #ifndef NDEBUG and #endif // NDEBUG is included for compilation only if the preprocessor macro NDEBUG is not defined.

Coventionally, NDEBUG is not defined for debug builds, and in that case our program would print out some extra diagnostic information to aid debugging/understanding the code.

This version of the program does not use any of the three things mentioned above;
do you understand this code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iomanip>

struct item
{
    int unique_number ;
    int start_time ;
    int end_time ;
};

// return true if a and b share the same open and close times
bool have_same_times( item a, item b )
{ return a.start_time == b.start_time && a.end_time == b.end_time ; }

// return a randomm position in the container of size container_size
// uses the legacy random number generator std::rand()
//      and a somewhat simplistic modulo division to fit the value in range
std::size_t random_pos( std::size_t container_size )
{ return std::rand() % container_size ; }

// return true if the two randomly selected items shared the same
// open and close times and they were swapped
bool random_swap( std::vector<item>& items )
{
    // pick the first item position at random
    const std::size_t pos_a = random_pos( items.size() ) ;

    // pick a different  second item position at random
    std::size_t pos_b = pos_a ;
    while( pos_b == pos_a ) pos_b = random_pos( items.size() ) ;

    // if they share the same open and close times, swap them
    if( have_same_times( items[pos_a], items[pos_b] ) )
    {
        using std::swap ;
        swap( items[pos_a], items[pos_b] ) ;
        return true ;
    }

    else return false ; // otherwise do nothing and return false
}

int main()
{
    std::srand( std::time(nullptr) ) ; // seed the legacy rng

    std::vector<item> items
    {
        {  1,  0, 24 },
        {  2,  0, 24 },
        {  3,  7, 24 },
        {  4,  0, 24 },
        {  5,  0,  7 },
        {  6,  7, 24 },
        {  7,  7, 24 },
        {  8,  0,  7 },
        {  9,  0, 24 },
        { 10, 0, 24 },
        { 11, 0, 24 },
        { 12, 7, 24 }
    };
    for( const item& it : items ) std::cout << std::setw(3) << it.unique_number ;
    std::cout << '\n' ;

    const int N = 12 ;

    for( int i = 0 ; i < N ; ++i )
    {
        const bool swapped = random_swap(items) ;
        if( swapped) // print out the modified order if items were wapped
        {
            std::cout << "\nafter iteration #" << i+1 << ":\n" ;
            for( const item& it : items ) std::cout << std::setw(3) << it.unique_number ;
            std::cout << '\n' ;
        }
    }
}

http://coliru.stacked-crooked.com/a/009c13baa4549c78
yat89 (81)
Hi FurryGuy,

But please, make some effort to answer questions on your own first.

I'm sorry for asking questions like that. Actually, I've been looking for everything I asked about. But it's hard for me to understand. Maybe because I'm not familiar with it. Furthermore, I have just learned this programming. Thanks for the link you provided earlier. For sure, I will study later. Again, thank you for the time you gave to read this post and I really appreciate it.

Hi JLBorges, thank you for your explanations.

This version of the program does not use any of the three things mentioned above;
do you understand this code?

Aahaa.. I think. this much better. I could understand the process. I will try to apply it into the following data.

1 2 3 4 5 6 7 8 9 10 11 12
11 9 7 5 3 12 10 8 6 4 2 1
12 6 5 4 7 8 9 3 2 1 11 10

Thank you very much for your patience in helping me. I will do it tomorrow.
I will be back if I have other issues on this.

Thank you. Have a nice day :)



closed account (E0p9LyTq)
@yat89, if you've already looked for answers on your own and still need help let us know you've tried. :)

Some people don't bother, they come here and expect us to do ALL the work for them.

Staring at code you've never seen before can be very scary. Especially when starting to learn C++. So much to learn even with the basics.

Sadly much of what is taught in schools, and how it is taught, is IMO sub-standard and outdated.

DO ask questions, they are a step to understanding. It will take time.


yat89 (81)
Hi JLBorges, sorry for the late reply.. just recover from fever.. I need to generated two random number for each row in which have same start and end times, then swap those numbers. I had try coded it, but errors came out. I don't know how to fix the errors? Do i coded it wrong? If yes, if you don't mind, could you please tell me where I need to fix it.

Any advice would greatly appreciated. 


1 2 3 4 5 6 7 8 9 10 11 12
11 9 7 5 3 12 10 8 6 4 2 1
12 6 5 4 7 8 9 3 2 1 11 10


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

struct item
{
	int stop_id;
	int start_time;
	int end_time;
};

// return true if a and b share the same open and close times
bool have_same_times(item a, item b)
{
	return a.start_time == b.start_time && a.end_time == b.end_time;
}

// return a randomm position in the container of size container_size
// uses the legacy random number generator std::rand()
//      and a somewhat simplistic modulo division to fit the value in range
size_t random_pos(size_t stop_id_size)
{
	return rand() % stop_id_size;
}

// return true if the two randomly selected items shared the same
// open and close times and they were swapped
bool random_swap(std::vector<int>& route)
{
	// pick the first item position at random
	const size_t pos_a = random_pos(route.size());

	// pick a different  second item position at random
	size_t pos_b = pos_a;
	while (pos_b == pos_a) pos_b = random_pos(route.size());

	// if they share the same open and close times, swap them
	if (have_same_times(route[pos_a], route[pos_b]))
	{
		//using std::swap;
		swap(route[pos_a], route[pos_b]);
		return true;
	}

	else return false; // otherwise do nothing and return false
}

int main()
{
	srand(time(nullptr)); // seed the legacy rng

	std::vector< std::vector<std::size_t> > route =
	{
		{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 },
		{ 11, 9, 7, 5, 3, 12, 10, 8, 6, 4, 2, 1 },
		{ 12, 6, 5, 4, 7, 8, 9, 3, 2, 1, 11, 10 }
	};
	for (const auto &vec : route)
	{
		for (int i : vec) cout << setw(3) << i;
		cout << '\n';
	}
	cout << '\n';

	std::vector<item> items
	{
		{  1,  0, 24 },
		{  2,  0, 24 },
		{  3,  7, 24 },
		{  4,  0, 24 },
		{  5,  0,  7 },
		{  6,  7, 24 },
		{  7,  7, 24 },
		{  8,  0,  7 },
		{  9,  0, 24 },
		{ 10, 0, 24 },
		{ 11, 0, 24 },
		{ 12, 7, 24 }
	};

	for (int i = 0; i < route.size(); ++i)
	{
		const bool swapped = random_swap(route);
		if (swapped) // print out the modified order if items were swapped
		{
			// Display new solution after swapping random numbers for each row
			for (const auto &vec : route)
			{
				for (int i : vec) cout << setw(3) << i;
				cout << '\n';
			}
			cout << '\n';
		}
	}
}


JLBorges (13770)
If I understand the problem correctly, something like this:

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

struct stop
{
    int stop_id ;
    int start_time ;
    int end_time ;
};

// return true if a and b share the same open and close times
bool have_same_times( stop a, stop b )
{ return a.start_time == b.start_time && a.end_time == b.end_time ; }

// return a random position in the container of size container_size
// uses the legacy random number generator std::rand()
//      and a somewhat simplistic modulo division to fit the value in range
std::size_t random_pos( std::size_t container_size )
{ return std::rand() % container_size ; }

// pick two random stop positions with the same start and end times
// invariant: for every stop, there is at least one other stop with the same start and end times
std::pair<int,int> random_stops_with_same_times( const std::vector<stop>& stops )
{
    // pick a random first stop
    const stop stop_a = stops[ random_pos( stops.size() ) ] ;

    // pick a different second stop with he same times at random
    stop stop_b = stop_a ;
    // caveat: unbounded loop
    while( stop_b.stop_id == stop_a.stop_id || have_same_times( stop_a, stop_b ) )
        stop_b = stops[ random_pos( stops.size() ) ] ;

    return std::make_pair( stop_a.stop_id, stop_b.stop_id ) ;
}

// swap two random stops with the same start and end times in the route
void random_swap( std::vector<int>& route, const std::vector<stop>& stops )
{
    // pick two random stops with the same start and end times
    const std::pair<int,int> stops_to_be_swapped = random_stops_with_same_times(stops) ;

    // locate the position of the stops in the route
    const auto iter_a = std::find( route.begin(), route.end(), stops_to_be_swapped.first ) ;
    const auto iter_b = std::find( route.begin(), route.end(), stops_to_be_swapped.second ) ;

    // swap them
    if( iter_a != route.end() && iter_b != route.end() )
    {
        std::cout << "swapping stops " << *iter_a << " and " << *iter_b << '\n' ;
        std::iter_swap( iter_a, iter_b ) ;
    }
}

void print_route( const std::vector<int>& route )
{
    for( int v : route ) std::cout << std::setw(3) << v ;
    std::cout << '\n' ;
}

int main()
{
    std::srand( std::time(nullptr) ) ; // seed the legacy rng

    // a route is a sequence of stops (identified by stop_ids)
    // every stop in included once in a route
    std::vector< std::vector<int> > routes =
    {
		{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 },
		{ 11, 9, 7, 5, 3, 12, 10, 8, 6, 4, 2, 1 },
		{ 12, 6, 5, 4, 7, 8, 9, 3, 2, 1, 11, 10 }
    };

    // stop_id, start_time and end_time for each stop
    std::vector<stop> stops
    {
        {  1,  0, 24 },
        {  2,  0, 24 },
        {  3,  7, 24 },
        {  4,  0, 24 },
        {  5,  0,  7 },
        {  6,  7, 24 },
        {  7,  7, 24 },
        {  8,  0,  7 },
        {  9,  0, 24 },
        { 10, 0, 24 },
        { 11, 0, 24 },
        { 12, 7, 24 }
    };

    for( auto& rt : routes )
    {
        print_route(rt) ;
        random_swap( rt, stops ) ;
        print_route(rt) ;
        std::cout << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/9d33641a8598806b
yat89 (81)
Hi JLBorges, thanks for your help. Really appreciated it. Sorry for troubling you again. I had try run the codes and the solution appear, but they select two random stops not the same end and start times.

For example, this is the obtained solution.

1 2 3 4 5 6 7 8 9 10 11 12 
swapping stops 9 and 8 
1 2 3 4 5 6 7 9 8 10 11 12

 11 9 7 5 3 12 10 8 6 4 2 1 
swapping stops 11 and 8 
8 9 7 5 3 12 10 11 6 4 2 1

 12 6 5 4 7 8 9 3 2 1 11 10 
swapping stops 11 and 3 
12 6 5 4 7 8 9 11 2 1 3 10


For example, the first route, start time for stop 9 and 8 are same but end time is differ. End time for stop 9 is 24, meanwhile end time for stop 8 is 7.
JLBorges (13770)
> but they select two random stops not the same end and start times.

There is a typo on line 35:
1
2
 
// while( stop_b.stop_id == stop_a.stop_id || have_same_times( stop_a, stop_b ) ) // typo
   while( stop_b.stop_id == stop_a.stop_id || !have_same_times( stop_a, stop_b ) ) // should have been


Corrected code with some additional debug scaffolding:

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

struct stop
{
    int stop_id ;
    int start_time ;
    int end_time ;
};

void print_stop( const stop& st )
{
    std::cout << "stop #" << std::setw(2) << st.stop_id
              << "{start:" << st.start_time
              << " end:" << st.end_time << "}\n" ;
}

// return true if a and b share the same open and close times
bool have_same_times( stop a, stop b )
{ return a.start_time == b.start_time && a.end_time == b.end_time ; }

// return a random position in the container of size container_size
// uses the legacy random number generator std::rand()
//      and a somewhat simplistic modulo division to fit the value in range
std::size_t random_pos( std::size_t container_size )
{ return std::rand() % container_size ; }

// pick two random stop positions with the same start and end times
// invariant: for every stop, there is at least one other stop with the same start and end times
std::pair<int,int> random_stops_with_same_times( const std::vector<stop>& stops )
{
    // pick a random first stop
    const stop stop_a = stops[ random_pos( stops.size() ) ] ;

    // pick a different second stop with he same times at random
    stop stop_b = stop_a ;
    // caveat: unbounded loop
    while( stop_b.stop_id == stop_a.stop_id || !have_same_times( stop_a, stop_b ) )
        stop_b = stops[ random_pos( stops.size() ) ] ;

    std::cout << "picked stops " ;
    print_stop(stop_a) ;
    std::cout << "         and " ;
    print_stop(stop_b) ;

    return std::make_pair( stop_a.stop_id, stop_b.stop_id ) ;
}

// swap two random stops with the same start and end times in the route
void random_swap( std::vector<int>& route, const std::vector<stop>& stops )
{
    // pick two random stops with the same start and end times
    const std::pair<int,int> stops_to_be_swapped = random_stops_with_same_times(stops) ;

    // locate the position of the stops in the route
    const auto iter_a = std::find( route.begin(), route.end(), stops_to_be_swapped.first ) ;
    const auto iter_b = std::find( route.begin(), route.end(), stops_to_be_swapped.second ) ;

    // swap them
    if( iter_a != route.end() && iter_b != route.end() )
    {
        std::cout << "swapping stops " << *iter_a << " and " << *iter_b << '\n' ;
        std::iter_swap( iter_a, iter_b ) ;
    }
}

void print_route( const std::vector<int>& route )
{
    for( int v : route ) std::cout << std::setw(3) << v ;
    std::cout << '\n' ;
}

int main()
{
    std::srand( std::time(nullptr) ) ; // seed the legacy rng

    // a route is a sequence of stops (identified by stop_ids)
    // every stop in included once in a route
    std::vector< std::vector<int> > routes =
	{
		{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 },
		{ 11, 9, 7, 5, 3, 12, 10, 8, 6, 4, 2, 1 },
		{ 12, 6, 5, 4, 7, 8, 9, 3, 2, 1, 11, 10 }
	};

    // stop_id, start_time and end_time for each stop
	std::vector<stop> stops
    {
        {  1,  0, 24 },
        {  2,  0, 24 },
        {  3,  7, 24 },
        {  4,  0, 24 },
        {  5,  0,  7 },
        {  6,  7, 24 },
        {  7,  7, 24 },
        {  8,  0,  7 },
        {  9,  0, 24 },
        { 10, 0, 24 },
        { 11, 0, 24 },
        { 12, 7, 24 }
    };

    for( auto& rt : routes )
    {
        print_route(rt) ;
        random_swap( rt, stops ) ;
        print_route(rt) ;
        std::cout << "\n\n" ;
    }
}

http://coliru.stacked-crooked.com/a/2b09fa8768965a63
yat89 (81)
Thank you so much JLBorges for your help.
Really appreciated.
Wishing you have a great day ahead!
yat89 (81)
Hi JLBorges, after a long while, if you don't mind, I would like to ask. Same problem as above, but I want to read the data from a text files. I had successfully read the first data which is route data. Also, I had try to read time data from text file and create a vector of struct. When I compile, no errors occurred but the solution not appeared. Can you check the code? Is the way I wrote the code for reading the time data from text file is wrong?

Any advice greatly appreciated. Thank you.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <sstream>
using namespace std;

struct stop
{
	int stop_id;
	int start_time;
	int end_time;
};


void print_stop(const stop& st)
{
	std::cout << "stop #" << std::setw(2) << st.stop_id
		<< "{start:" << st.start_time
		<< " end:" << st.end_time << "}\n";
}


// return true if a and b share the same open and close times
bool have_same_times(stop a, stop b)
{
	return a.start_time == b.start_time && a.end_time == b.end_time;
}

// return a random position in the container of size container_size
// uses the legacy random number generator std::rand()
//      and a somewhat simplistic modulo division to fit the value in range
std::size_t random_pos(std::size_t container_size)
{
	return std::rand() % container_size;
}

// pick two random stop positions with the same start and end times
// invariant: for every stop, there is at least one other stop with the same start and end times
std::pair<int, int> random_stops_with_same_times(const std::vector<stop>& stops)
{
	// pick a random first stop
	const stop stop_a = stops[random_pos(stops.size())];

	// pick a different second stop with he same times at random
	stop stop_b = stop_a;
	// caveat: unbounded loop
	while (stop_b.stop_id == stop_a.stop_id || !have_same_times(stop_a, stop_b))
		stop_b = stops[random_pos(stops.size())];

	std::cout << "picked stops ";
	print_stop(stop_a);
	std::cout << "         and ";
	print_stop(stop_b);

	return std::make_pair(stop_a.stop_id, stop_b.stop_id);
}

// swap two random stops with the same start and end times in the route
void random_swap(std::vector<int>& route, const std::vector<stop>& stops)
{
	// pick two random stops with the same start and end times
	const std::pair<int, int> stops_to_be_swapped = random_stops_with_same_times(stops);

	// locate the position of the stops in the route
	const auto iter_a = std::find(route.begin(), route.end(), stops_to_be_swapped.first);
	const auto iter_b = std::find(route.begin(), route.end(), stops_to_be_swapped.second);

	// swap them
	if (iter_a != route.end() && iter_b != route.end())
	{
		std::cout << "swapping stop " << *iter_a << " and " << *iter_b << '\n';
		std::iter_swap(iter_a, iter_b);
	}
}

void print_route(const std::vector<int>& route)
{
	for (int v : route) std::cout << std::setw(3) << v;
	std::cout << '\n';
}

int main()
{
	std::srand(std::time(nullptr)); // seed the legacy rng

	ifstream route("routes.txt");
	vector<vector<int>> routes;

	for (string line; getline(route, line); )
	{
		routes.push_back(vector<int>());
		istringstream iss(line);
		for (int n; iss >> n; )
			routes.back().push_back(n);
	}

	ifstream time("times.txt");
	vector<stop> stops;

	for (string line; getline(time, line); )
	{
		istringstream iss(line);
		stop s;
		if (iss >> s.stop_id >> s.start_time >> s.end_time)
		{
			stops.push_back(s);
		}
	}

	for (auto& rt : routes)
	{
		print_route(rt);
		random_swap(rt, stops);
		print_route(rt);
		std::cout << "\n\n";
	}
}
JLBorges (13770)
> Is the way I wrote the code for reading the time data from text file is wrong?

Seems fine. Add some error checking code. For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
ifstream time("times.txt");
if( !time.is_open() )
{
    std::cout << "error opening times file\n" ;
    return 1 ;
}

vector<stop> stops;

for (string line; getline(time, line); )
{
    istringstream iss(line);
    stop s;

    if (iss >> s.stop_id >> s.start_time >> s.end_time)
    {
        std::cout << "succesfully read: " ;
        print_stop(s) ;
        stops.push_back(s);
    }

    else std::cout << "badly formed line '" << line << "' ignored\n" ;
}

yat89 (81)
Thanks JLBorges for your advice. I had add some error checking. Error opening times file appeared. Just noticed, I mistyped the text file.
Topic archived. No new replies allowed.