linear search for number vector in c++

Question

I am trying to output 9 random non repeating numbers. This is what I've been trying to do:

    #include <iostream>
#include <cmath>
#include <vector>
#include <ctime>
using namespace std;
int main() {
    srand(time(0));
    vector<int> v;
    for (int i = 0; i<4; i++) {
        v.push_back(rand() % 10);
    }
    for (int j = 0; j<4; j++) {
        for (int m = j+1; m<4; m++) {
                while (v[j] == v[m]) {
                    v[m] = rand() % 10;
                }
        }
        cout << v[j];
    }
}

However, i get repeating numbers often. Any help would be appreciated. Thank you.

Nitpick: Random numbers may very well repeat - in fact if you prevent repeating numbers they are no longer random — UnholySheep, Apr 11 '18 at 07:38
Possible duplicate of [Generating random non repeating number array in C++](https://stackoverflow.com/questions/25878202/generating-random-non-repeating-number-array-in-c) — UnholySheep, Apr 11 '18 at 07:39

Bathsheba · Answer 1 · 2018-04-11T08:20:31.640

2

With a true random number generator, the probability of drawing a particular number is not conditional on any previous numbers drawn. I'm sure you've attained the same number twice when rolling dice, for example.

rand(), which roughly approximates a true generator, will therefore give you back the same number; perhaps even consecutively: your use of % 10 further exacerbates this.

If you don't want repeats, then instantiate a vector containing all the numbers you want potentially, then shuffle them. std::shuffle can help you do that.

See http://en.cppreference.com/w/cpp/algorithm/random_shuffle

edited Apr 11 '18 at 08:20

answered Apr 11 '18 at 07:45

Bathsheba

231,907
34
361
483

This does not solve the OP's specific problem (what's wrong with their code), so it doesn't really help in this specific case. I think it should be posted on the duplicate target instead. – user202729 Apr 11 '18 at 07:47
@user202729: What makes you say that? Do you have further information on the usage requirements? – Bathsheba Apr 11 '18 at 07:48
1

@user202729: In your opinion. In mine it's sufficient to point out that the algorithm is defective, and the reason why. Pointing out the specific defects in the implementation is therefore of no benefit. There's no harm in your answering though. As for performance, the bottleneck will be in the `cout`, not Fisher Yates on a set of 10 numbers. – Bathsheba Apr 11 '18 at 07:51
If your answer only contains that, vote to close as duplicate is (IMO) better. Although... this is slightly better as it explains why does `rand()` generates duplicate numbers. Not sure if it worths it. – user202729 Apr 11 '18 at 07:53
@user202729: But do answer though - there's still time. And I would upvote if I liked it. Voting is never to be taken personally. – Bathsheba Apr 11 '18 at 07:54
Shubham's answer should cover everything is wrong about OP's code (and so should help the OP to fix their own code). I don't think I need to post another answer. – user202729 Apr 11 '18 at 07:57

Shubham · Answer 2 · 2018-04-11T19:25:07.563

1

When j=0, you'll be checking it with m={1, 2, 3} But when j=1, you'll be checking it with just m={2, 3}.

You are not checking it with the 0th index again. There, you might be getting repetitions.

Also, note to reduce the chances of getting repeated numbers, why not increase the size of random values, let's say maybe 100.

Please look at the following code to get distinct random values by constantly checking the used values in a std::set:

#include <iostream>
#include <vector>
#include <set>

int main() {

    int n = 4;
    std::vector <int> values(n);
    std::set <int> used_values;

    for (int i = 0; i < n; i++) {
        int temp = rand() % 10;
        while (used_values.find(temp) != used_values.end())
            temp = rand() % 10;
        values[i] = temp;
    }

    for(int i = 0; i < n; i++) 
        std::cout << values[i] << std::endl;

    return 0;
}

edited Apr 11 '18 at 19:25

answered Apr 11 '18 at 07:42

Shubham

2,847
4
24
37

Do you have any suggestions on how to fix this problem? – matt Apr 11 '18 at 08:01
1

Yes. Suppose you already have filled `k` distinct values in `n` sized array. Also, these `k` numbers will have to be present in the set. Now to put the `k+1`th index, generate a random number and check if it is present in the set. If not, then assign it to that position, else repeat. – Shubham Apr 11 '18 at 08:12
i don't clearly understand what you are trying to do – matt Apr 11 '18 at 16:05
@matt Please look at the updated answer. I have provided the code to clarify what I was explaining in the comments. – Shubham Apr 11 '18 at 19:25
the updated answer keeps giving me the same random unique number every time i run the program instead of giving me different random unique number every time i run the program – matt Apr 12 '18 at 20:44
@matt That's because the numbers are actually pseudo random numbers. You can use the `srand()` to specify a seed value if you wish to. – Shubham Apr 14 '18 at 07:28
@matt You should also read about this here: [https://stackoverflow.com/a/7748374/3160529](https://stackoverflow.com/a/7748374/3160529) – Shubham Apr 14 '18 at 07:33

linear search for number vector in c++

2 Answers2