Java. Старайтесь избегать дубликатов при использовании случайных для получения строк в текстовом файле [дубликат]

Вместо того, чтобы делать все это, создайте объект LinkedHashSet и случайные числа для него функцией Math.random() .... если какая-либо повторяющаяся запись происходит, объект LinkedHashSet не добавит этот номер в свой список ... Так как в этом классе коллекций не допускаются повторяющиеся значения. В конце вы получите список случайных чисел, не имеющих дублирующихся значений ....: D

//random numbers are 0,1,2,3 
ArrayList<Integer> numbers = new ArrayList<Integer>();   
Random randomGenerator = new Random();
while (numbers.size() < 4) {

    int random = randomGenerator .nextInt(4);
    if (!numbers.contains(random)) {
        numbers.add(random);
    }
}

На самом деле все зависит от того, для чего вам нужна случайная генерация, но вот мое занятие.

Сначала создайте автономный метод для генерации случайного числа. Обязательно допустим ограничения.

public static int newRandom(int limit){
    return generatedRandom.nextInt(limit);  }

Затем вам нужно создать очень простую структуру принятия решений, которая сравнивает значения. Это можно сделать одним из двух способов. Если у вас есть очень ограниченное количество чисел для проверки, достаточно простого оператора IF:

public static int testDuplicates(int int1, int int2, int int3, int int4, int int5){
    boolean loopFlag = true;
    while(loopFlag == true){
        if(int1 == int2 || int1 == int3 || int1 == int4 || int1 == int5 || int1 == 0){
            int1 = newRandom(75);
            loopFlag = true;    }
        else{
            loopFlag = false;   }}
    return int1;    }

Вышеприведенное сравнивает int1 с int2 через int5, а также гарантирует отсутствие нулей в randoms.

Используя эти два метода, мы можем сделать следующее:

    num1 = newRandom(limit1);
    num2 = newRandom(limit1);
    num3 = newRandom(limit1);
    num4 = newRandom(limit1);
    num5 = newRandom(limit1);

Followed:

        num1 = testDuplicates(num1, num2, num3, num4, num5);
        num2 = testDuplicates(num2, num1, num3, num4, num5);
        num3 = testDuplicates(num3, num1, num2, num4, num5);
        num4 = testDuplicates(num4, num1, num2, num3, num5);
        num5 = testDuplicates(num5, num1, num2, num3, num5);

Если у вас есть более длинный список для проверки, то более сложный метод даст лучшие результаты как в ясности кода, так и в обработке ресурсов.

Надеюсь, это поможет. Этот сайт мне очень помог, я чувствовал себя обязанным, по крайней мере, ПОПРОБОВАТЬ, чтобы помочь.

Самый эффективный, основной способ иметь неповторяющиеся случайные числа объясняется этим псевдокодом. Нет необходимости иметь вложенные циклы или хешированные запросы:

// get 5 unique random numbers, possible values 0 - 19
// (assume desired number of selections < number of choices)

const int POOL_SIZE = 20;
const int VAL_COUNT = 5;

declare Array mapping[POOL_SIZE];
declare Array results[VAL_COUNT];

declare i int;
declare r int;
declare max_rand int;

// create mapping array
for (i=0; i<POOL_SIZE; i++) {
   mapping[i] = i;
}

max_rand = POOL_SIZE-1;  // start loop searching for maximum value (19)

for (i=0; i<VAL_COUNT; i++) {
    r = Random(0, max_rand); // get random number
    results[i] = mapping[r]; // grab number from map array
    mapping[r] = max_rand;  // place item past range at selected location

    max_rand = max_rand - 1;  // reduce random scope by 1
}

Предположим, что первая итерация генерирует случайное число 3 для начала (от 0 до 19). Это сделало бы результаты [0] = сопоставление [3], т. Е. Значение 3. Затем мы присвоили отображение [3] равным 19.

На следующей итерации случайное число было 5 (из 0-18). Это дало бы результаты [1] = mapping [5], т. Е. Значение 5. Затем мы назначили отображение [5] на 18.

Теперь предположим, что следующая итерация снова выбрала 3 (из 0 - 17). результатам [2] присваивается значение отображения [3], но теперь это значение не равно 3, но 19.

Эта же защита сохраняется для всех чисел, даже если у вас есть тот же номер 5 раз подряд. Например, если генератор случайных чисел дал вам 0 пять раз подряд, результаты будут следующими: [0, 19, 18, 17, 16].

Вы никогда не получите одинаковый номер дважды.

Другой подход, который позволяет вам указать, сколько чисел вы хотите с size и min и max значения возвращаемых чисел

public static int getRandomInt(int min, int max) {
    Random random = new Random();

    return random.nextInt((max - min) + 1) + min;
}

public static ArrayList<Integer> getRandomNonRepeatingIntegers(int size, int min,
        int max) {
    ArrayList<Integer> numbers = new ArrayList<Integer>();

    while (numbers.size() < size) {
        int random = getRandomInt(min, max);

        if (!numbers.contains(random)) {
            numbers.add(random);
        }
    }

    return numbers;
}

Чтобы использовать его, возвращая 7 чисел между 0 и 25.

    ArrayList<Integer> list = getRandomNonRepeatingIntegers(7, 0, 25);
    for (int i = 0; i < list.size(); i++) {
        System.out.println("" + list.get(i));
    }

Вот как я это сделал

import java.util.ArrayList;
import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int size = 20;

        ArrayList<Integer> list = new ArrayList<Integer>(size);
        for(int i = 1; i <= size; i++) {
            list.add(i);
        }

        Random rand = new Random();
        while(list.size() > 0) {
            int index = rand.nextInt(list.size());
            System.out.println("Selected: "+list.remove(index));
        }
    }
}

Как отметил уважаемый мистер Скит: Если n - количество случайно выбранных номеров, которые вы хотите выбрать, и N - общее пространство выборки доступных для выбора чисел:

1. Если n & lt; N , вы должны просто сохранить числа, которые вы выбрали, и проверить список, чтобы узнать, находится ли в нем выбранный номер.
2. Если n ~ = N , вы, вероятно, должны использовать мой метод, заполнив список, содержащий все пространство выборки, а затем удалите из него номера по мере их выбора.

Здесь - эффективное решение для быстрого создания рандомизированного массива. После рандомизации вы можете просто выбрать n -й элемент e массива, increment n и return e. Это решение имеет O (1) для получения случайного числа и O (n) для инициализации, но поскольку компромисс требует хорошего объема памяти, если n становится достаточно большим.

Существует другой способ делать «случайные» упорядоченные числа с LFSR, взгляните на:

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

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

Но это не истинные случайные числа, потому что случайная генерация детерминирована [/. g4]

Но в зависимости от вашего случая вы можете использовать эту технику, уменьшая количество обработки при генерации случайных чисел при использовании тасования.

Здесь алгоритм LFSR в java (я взял его где-то, я не remeber):

public final class LFSR {
    private static final int M = 15;

    // hard-coded for 15-bits
    private static final int[] TAPS = {14, 15};

    private final boolean[] bits = new boolean[M + 1];

    public LFSR() {
        this((int)System.currentTimeMillis());
    }

    public LFSR(int seed) {
        for(int i = 0; i < M; i++) {
            bits[i] = (((1 << i) & seed) >>> i) == 1;
        }
    }

    /* generate a random int uniformly on the interval [-2^31 + 1, 2^31 - 1] */
    public short nextShort() {
        //printBits();

        // calculate the integer value from the registers
        short next = 0;
        for(int i = 0; i < M; i++) {
            next |= (bits[i] ? 1 : 0) << i;
        }

        // allow for zero without allowing for -2^31
        if (next < 0) next++;

        // calculate the last register from all the preceding
        bits[M] = false;
        for(int i = 0; i < TAPS.length; i++) {
            bits[M] ^= bits[M - TAPS[i]];
        }

        // shift all the registers
        for(int i = 0; i < M; i++) {
            bits[i] = bits[i + 1];
        }

        return next;
    }

    /** returns random double uniformly over [0, 1) */
    public double nextDouble() {
        return ((nextShort() / (Integer.MAX_VALUE + 1.0)) + 1.0) / 2.0;
    }

    /** returns random boolean */
    public boolean nextBoolean() {
        return nextShort() >= 0;
    }

    public void printBits() {
        System.out.print(bits[M] ? 1 : 0);
        System.out.print(" -> ");
        for(int i = M - 1; i >= 0; i--) {
            System.out.print(bits[i] ? 1 : 0);
        }
        System.out.println();
    }


    public static void main(String[] args) {
        LFSR rng = new LFSR();
        Vector<Short> vec = new Vector<Short>();
        for(int i = 0; i <= 32766; i++) {
            short next = rng.nextShort();
            // just testing/asserting to make 
            // sure the number doesn't repeat on a given list
            if (vec.contains(next))
                throw new RuntimeException("Index repeat: " + i);
            vec.add(next);
            System.out.println(next);
        }
    }
}

Существует более эффективное и менее громоздкое решение для целых чисел, чем Collections.shuffle.

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

Этот алгоритм работает для загрузки любого массива и достижения случайного порядка в конце загрузки. Он также работает для добавления в коллекцию List (или любой другой индексированной коллекции) и достижения случайной последовательности в коллекции в конце добавлений.

Это можно сделать с помощью одного массива, созданного один раз, или с помощью численного заказа, например списка. Для массива размер исходного массива должен быть точного размера, чтобы содержать все заданные значения. Если вы не знаете, сколько значений может произойти заблаговременно, использование набора с упорядоченным числом, например ArrayList или List, где размер не является неизменным, также будет работать. Он будет работать универсально для массива любого размера до Integer.MAX_VALUE, который составляет чуть более 2 000 000 000. Объекты списка будут иметь одинаковые пределы индекса. Когда вы дойдете до массива такого размера, на вашем компьютере может закончиться нехватка памяти. Может быть более эффективным загрузить массив, набранный для типов объектов, и преобразовать его в некоторую коллекцию после загрузки массива. Это особенно верно, если целевая коллекция не индексируется численно.

Этот алгоритм, точно так же, как написано, создаст очень ровное распределение, где дубликатов нет. Один из аспектов, который ОЧЕНЬ ВАЖНО, заключается в том, что он должен иметь возможность вхождения следующего элемента в текущий текущий размер + 1. Таким образом, для второго элемента можно было бы сохранить его в местоположении 0 или местоположении 1 . Для 20-го элемента можно сохранить его в любом месте, от 0 до 19. Как можно больше первый элемент останется в местоположении 0, так как он должен попасть в любое другое место. Это возможно, так как следующий новый пункт отправится куда угодно, включая следующее новое место.

Случайность последовательности будет такой же случайной, как случайность генератора случайных чисел.

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

// RandomSequence.java
import java.util.Random;
public class RandomSequence {

    public static void main(String[] args) {
        // create an array of the size and type for which
        // you want a random sequence
        int[] randomSequence = new int[20];
        Random randomNumbers = new Random();

        for (int i = 0; i < randomSequence.length; i++ ) {
            if (i == 0) { // seed first entry in array with item 0
                randomSequence[i] = 0; 
            } else { // for all other items...
                // choose a random pointer to the segment of the
                // array already containing items
                int pointer = randomNumbers.nextInt(i + 1);
                randomSequence[i] = randomSequence[pointer]; 
                randomSequence[pointer] = i;
                // note that if pointer & i are equal
                // the new value will just go into location i and possibly stay there
                // this is VERY IMPORTANT to ensure the sequence is really random
                // and not biased
            } // end if...else
        } // end for
        for (int number: randomSequence) {
                System.out.printf("%2d ", number);
        } // end for
    } // end main
} // end class RandomSequence

Существует алгоритм пакетной карты: вы создаете упорядоченный массив чисел («пакет карт»), и на каждой итерации вы выбираете номер в произвольной позиции (удалив выбранный номер из «карточной партии», конечно) .

Вы можете использовать один из классов, реализующих интерфейс Set ( API ), а затем каждый номер, который вы создаете, используйте Set.add () для его вставки.

Если возвращаемое значение ложно, вы знаете, что номер уже создан раньше.

Ваша проблема, похоже, сводится к выбору k элементов случайным образом из набора из n элементов. Таким образом, запрос Collections.shuffle является правильным, но, как указано, неэффективен: его O (n).

Википедия: Fisher-Yates shuffle имеет версию O (k), когда массив уже существует. В вашем случае нет массива элементов, и создание массива элементов может быть очень дорогостоящим, скажем, если max было 10000000 вместо 20.

Алгоритм тасования включает инициализацию массива размера n, где каждый элемент равен его индексу, подбирая k случайных чисел каждое число в диапазоне с максимальным, меньшим, чем предыдущий диапазон, затем заменяя элементы на конец массива.

Вы можете сделать ту же операцию в O (k) время с помощью hashmap, хотя я признаю ее вид боли. Заметим, что это стоит того, если k намного меньше n. (т. е. k ~ lg (n) или так), в противном случае вы должны использовать тасование напрямую.

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

1. Выберите k случайных чисел: первый находится в диапазоне от 0 до n-1, второй от 0 до n-2, третий от 0 до n-3 и т. д., через n-k.
2. Рассматривайте свои случайные числа как набор свопов. Первый случайный индекс переходит в конечную позицию. Второй случайный индекс свопит во вторую и последнюю позицию. Однако вместо того, чтобы работать с массивом поддержки, работайте против вашего хэшмапа. Ваш хэш-файл сохранит все позиции, которые находятся вне позиции.

int getValue(i)
{
    if (map.contains(i)) 
        return map[i];
    return i;
}

void setValue(i, val)
{   
    if (i == val)
        map.remove(i);
    else
        map[i] = val;
}

int[] chooseK(int n, int k)
{
    for (int i = 0; i < k; i++)
    {
        int randomIndex = nextRandom(0, n - i); //(n - i is exclusive)
        int desiredIndex = n-i-1;

        int valAtRandom = getValue(randomIndex);
        int valAtDesired = getValue(desiredIndex);

        setValue(desiredIndex, valAtRandom);
        setValue(randomIndex, valAtDesired);
    }

    int[] output = new int[k];
    for (int i = 0; i < k; i++)
    {
        output[i] = (getValue(n-i-1));
    }

    return output;
}