Рандом без повторений

@Shef4u · Регистрация: 31.10.2011

Author24 — интернет-сервис помощи студентам

Здравствуйте! Искал по форуме, но так и не нашел подходящее решение такой задачи:
пользователь вводит К ПРИМЕРУ число 7. я беру от него логарифм за основанием 2 и заокругляю к большему n=ceil(log(Np)/log(2)); это выйдет n=3. ага, теперь я знаю, что мне надо 7 комбинаций по 3 символа в двочином коде не считая 000 так как всего может быть восемь: 000 111 100 101 011 001 110 010. 000 мне не надо. внимание вопрос: как это сделать через rand или как-то иначе?? вот мой код, но в нем числа повторяютя и комбинация 000 присутствует((

Код

int Np;
float n;
cout<<"Введите Np="; cin>>Np;
n=ceil(log(Np)/log(2));
cout<<"n="<<n<<endl;
randomize();
for (int i=0; i<Np; i++)
{
  for (int j=0; j<n; j++)
cout<<rand()%2;
cout<<endl;      
}

Добавлено через 3 часа 7 минут
покапался еще на форуме и нашел вариант с записью в массив и потом сравнением. как тогда записать в цикле значение в массив? если просто написать

C++

int Np, *mas=new int[Np];
float n;
cout<<"Введите Np="; cin>>Np;
n=ceil(log(Np)/log(2));
cout<<"n="<<n<<endl;
randomize();
for (int i=0; i<Np; i++)
{
  for (int j=0; j<n; j++)
cout<<rand()%2; cin>>mas[i];
cout<<endl;      
}

не подходит ((

@Ev[G]eN · 15.03.2013, 22:15

так?

C++

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
int main ()
{
    srand(time(0));
 
    int Np;
    std::cout << "Input Np: ";
    std::cin >> Np;
 
    int n = ceil(log(Np) / log(2));
    std::cout << "N: " << n << std::endl;
 
    int fLimit = pow(10, n - 1) - 1;
    int sLimit = pow(10, n);
    int *array = new int [Np];
    for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }
 
    std::cout << "Your array: " << std::endl;
    for (int i = 0; i < Np; i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;
 
    delete [] array;
    return 0;
}

@Shef4u · 15.03.2013, 22:30 **[ТС]**

Сообщение от Ev[G]eN

так?

C++

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
int main ()
{
    srand(time(0));
 
    int Np;
    std::cout << "Input Np: ";
    std::cin >> Np;
 
    int n = ceil(log(Np) / log(2));
    std::cout << "N: " << n << std::endl;
 
    int fLimit = pow(10, n - 1) - 1;
    int sLimit = pow(10, n);
    int *array = new int [Np];
    for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }
 
    std::cout << "Your array: " << std::endl;
    for (int i = 0; i < Np; i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;
 
    delete [] array;
    return 0;
}

спасибо, cmath не работало, по этому заменил на math.h . Да и выводит не то что мне надо

@Shef4u · 15.03.2013, 22:32 **[ТС]**

Сообщение от Ev[G]eN

так?

C++

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
int main ()
{
    srand(time(0));
 
    int Np;
    std::cout << "Input Np: ";
    std::cin >> Np;
 
    int n = ceil(log(Np) / log(2));
    std::cout << "N: " << n << std::endl;
 
    int fLimit = pow(10, n - 1) - 1;
    int sLimit = pow(10, n);
    int *array = new int [Np];
    for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }
 
    std::cout << "Your array: " << std::endl;
    for (int i = 0; i < Np; i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;
 
    delete [] array;
    return 0;
}

можете написать кусок кода который будет делать каждый раз проверку, не равен ли результат какому-либо из уже полученных и, если равен, вызывать rand()%2 ещё раз b еще раз?

@Ev[G]eN · 15.03.2013, 22:34

Сообщение от Shef4u

кусок кода который будет делать каждый раз проверку, не равен ли результат какому-либо из уже полученных

C++

for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }

@Shef4u · 15.03.2013, 22:42 **[ТС]**

Сообщение от Ev[G]eN

C++

for (int i = 0; i < Np; i++) {
        int genElem = (rand() % (sLimit - fLimit + 1));
        if (!std::count(array, array + Np, genElem))
            array[i] = genElem;
        else
            i--;
    }

может вам что-нибудь известно о синтаксисе де Брейновской ф-ции?
де Брейновская функция это булева функция порождающая псевдослучацную последовательность длины 2^n.
Важное свойство: Все числа в этой последовательности различны и находятся в диапазоне от 0 до 2^n.
де Брейновская функция для n = 3:
|x2|x1|x0|f|
| 0| 0| 0|1|
| 0| 0| 1|0|
| 0| 1| 0|1|
| 0| 1| 1|1|
| 1| 0| 0|0|
| 1| 0| 1|1|
| 1| 1| 0|0|
| 1| 1| 1|0|

@0x10 · 16.03.2013, 07:49

Shef4u, как я понимаю, диапазон значений известен, допустимые значения известны - заполняем массив и перемешиваем std::random_shuffle.

Ev[G]eN, ну вот не надо такой "угадайки". Будем кидать рандом до посинения пока не найдем неиспользованное число? И сколько раз оно сработает в ситуации, когда нужно получить случайную последовательность размером 100 со значениями в диапазоне от 0 до 99, когда остался незаполненным один последний элемент?

@Vaste · 16.03.2013, 08:16

Кидай сгенерированные значения в массив, чтоб смореть было или нет. Иначе никак.

@olea · 28.04.2013, 13:07

Shef4u, а не могли бы вы привести синтаксис де Брейновской функции?

@Shef4u · 29.04.2013, 16:52 **[ТС]**

Сообщение от olea

Shef4u, а не могли бы вы привести синтаксис де Брейновской функции?

если б я его знал

MrGluck · 29.04.2013, 16:55

Делается все так:
берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс.

Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов.

Ternsip · 29.04.2013, 16:58

C++

#include <iostream>
#include <vector>
#include <ctime>  
 
using namespace std;
 
int main(){            
    std::srand ( unsigned ( std::time(0) ) );
    vector <int> a;
    int n = 100;
    for (int i = 0; i < n; i++) {
        a.push_back(i);
    }
    std::random_shuffle(a.begin(), a.end());
    for (int i = 0; i < a.size(); i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

Добавлено через 16 секунд
MrGluck, эххх, вы меня обогнали))

MrGluck · 29.04.2013, 16:59

Ternsip,

C++

1 2	#include <cstdlib> #include <algorithm>

Ternsip · 29.04.2013, 17:01

MrGluck, в Microsoft Visual C++ 2012 уже не нужно

MrGluck · 29.04.2013, 17:07

Ternsip, ничто не гарантирует, что данные хедеры подключатся какими-то косыми-кривыми путями. Если используете функцию из файла - укажите явно где её искать.

Если что, mingw не пропустит random_shuffle, а gcc еще и на srand ругнется.

Добавлено через 1 минуту
Кстати, правила п.5.10 прочтите.
Как бы ни хотелось - но закон есть закон.

@Shef4u · 01.05.2013, 21:42 **[ТС]**

Сообщение от MrGluck

Делается все так:
берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс.

Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов.

спасибо, но что делать если всеможможных значений 36 и больше? не записывать же все в массив. и что вы имели ввиду под сдвигом индекса? побитовое? >>

@0x10 · 01.05.2013, 21:47

Сообщение от Shef4u

спасибо, но что делать если всеможможных значений 36 и больше?

Мелочевка.

Сообщение от Shef4u

и что вы имели ввиду под сдвигом индекса? побитовое? >>

Уже столько раз обсасывалось, что даже отвечать лень... У тебя есть массив array из N случайных чисел. Если нужно K чисел, то выбираешь array[i] где i = [0..K]. Если нужно очередное число, берешь i+1.

MrGluck · 01.05.2013, 23:10

Shef4u, вы считаете, что каждый раз тыкаться по всему массиву из n чисел, проверяя есть ли данное число в массиве и если нет - повторять операцию до посинения - лучший вариант? Нет, к сожалению более производительного решения, чем я предложил нет. Да и недолго это на ЭВМ то.

Сообщение от Shef4u

сдвигом индекса

инкремент

@nonedark2008 · 02.05.2013, 00:36

По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута.

@Shef4u · 03.05.2013, 11:44 **[ТС]**

Сообщение от nonedark2008

По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута.

спасибо. наслышан уже об этой книге от профессора который ведет теорию вероятности но все никак не дойдут руки прочесть

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	29.04.2013, 17:01	14
	MrGluck, в Microsoft Visual C++ 2012 уже не нужно 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	01.05.2013, 23:10	18
	Shef4u, вы считаете, что каждый раз тыкаться по всему массиву из n чисел, проверяя есть ли данное число в массиве и если нет - повторять операцию до посинения - лучший вариант? Нет, к сожалению более производительного решения, чем я предложил нет. Да и недолго это на ЭВМ то. Сообщение от Shef4u сдвигом индекса инкремент 1

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	02.05.2013, 00:36	19
	По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута. 0

@0x10 3257 / 2059 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	16.03.2013, 07:49	7
	Shef4u, как я понимаю, диапазон значений известен, допустимые значения известны - заполняем массив и перемешиваем std::random_shuffle. Ev[G]eN, ну вот не надо такой "угадайки". Будем кидать рандом до посинения пока не найдем неиспользованное число? И сколько раз оно сработает в ситуации, когда нужно получить случайную последовательность размером 100 со значениями в диапазоне от 0 до 99, когда остался незаполненным один последний элемент? 0

@Vaste 1 / 1 / 0 Регистрация: 23.04.2012 Сообщений: 42
	16.03.2013, 08:16	8
	Кидай сгенерированные значения в массив, чтоб смореть было или нет. Иначе никак. 0

@olea 5 / 5 / 2 Регистрация: 30.01.2012 Сообщений: 153
	28.04.2013, 13:07	9
	Shef4u, а не могли бы вы привести синтаксис де Брейновской функции? 0

@Shef4u 15 / 15 / 4 Регистрация: 31.10.2011 Сообщений: 116
	29.04.2013, 16:52 [ТС]	10
	Сообщение от olea Shef4u, а не могли бы вы привести синтаксис де Брейновской функции? если б я его знал 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	29.04.2013, 16:55	11
	Делается все так: берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс. Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов. 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	29.04.2013, 17:07	15
	Ternsip, ничто не гарантирует, что данные хедеры подключатся какими-то косыми-кривыми путями. Если используете функцию из файла - укажите явно где её искать. Если что, mingw не пропустит random_shuffle, а gcc еще и на srand ругнется. Добавлено через 1 минуту Кстати, правила п.5.10 прочтите. Как бы ни хотелось - но закон есть закон. 1

@Shef4u 15 / 15 / 4 Регистрация: 31.10.2011 Сообщений: 116
	01.05.2013, 21:42 [ТС]	16
	Сообщение от MrGluck Делается все так: берется массив, заполняется всеми возможными значениями, далее с помощью std::random_shuffle перемешивается, и, если нам нужно получить новое "неповторяющееся число" - берем следующий элемент массива, сдвигая индекс. Я уже раз 5 отвечал на данный вопрос, не верю, что в поиске не было результатов. спасибо, но что делать если всеможможных значений 36 и больше? не записывать же все в массив. и что вы имели ввиду под сдвигом индекса? побитовое? >> 0

@0x10 3257 / 2059 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	01.05.2013, 21:47	17
	Сообщение от Shef4u спасибо, но что делать если всеможможных значений 36 и больше? Мелочевка. Сообщение от Shef4u и что вы имели ввиду под сдвигом индекса? побитовое? >> Уже столько раз обсасывалось, что даже отвечать лень... У тебя есть массив array из N случайных чисел. Если нужно K чисел, то выбираешь array[i] где i = [0..K]. Если нужно очередное число, берешь i+1. 0

@Shef4u 15 / 15 / 4 Регистрация: 31.10.2011 Сообщений: 116
	03.05.2013, 11:44 [ТС]	20
	Сообщение от nonedark2008 По мне так генерировать последовательность неповторяющихся простых чисел оптимальнее всего было бы с использованием конгруэнтного метода, который замечательно описан во втором томе Кнута. спасибо. наслышан уже об этой книге от профессора который ведет теорию вероятности но все никак не дойдут руки прочесть 0