Fast way to generate random columns elements

Question

I have a simple problem and I need a fast way to achieve that. Suppose I have two columns like

1 6 
3 5
5 3

As you see, element 3, and 5 are there in the 2nd column, I would like to generate a new random elements in column one, such that there will be no elements in the 2nd column matched. The elements can be from 1 ->12

My approach : I have added all the elements in the 2nd column to a hash set, then I search for the elements in column one, and check if they are in the hash set, if that's true, try to generate a new random element.

I have another idea is to visualize the problem as a 1D array, remove the duplicates,..etc., but I don't want to modify any elements in the 2nd Array.

Why does your approach fail when the second column has duplicate numbers? — tskuzzy, Nov 12 '13 at 00:12
because you need again to have another loop to check if the chosen random number is again in the set or no, and that's add more to the overall complexity — andre_lamothe, Nov 12 '13 at 00:14
Possible duplicate of http://stackoverflow.com/questions/14935997/generate-random-numbers-except-certain-values — Leeor, Nov 12 '13 at 00:14
@Trying no problem, but it would better to not have all the first columns duplicated elements — andre_lamothe, Nov 12 '13 at 00:15

Trying · Answer 1 · 2013-11-12T00:29:26.773

0

Put the column2 values to HashSet.
Just use (Math.random() * 12)+1 which will generate number form 1 to 12.
Now search whether the number generated is present in set if present in set than regenerate i.e. go to step 2, else done.

Hope it helps.

EDIT

O(1)

I am taking just a a small sample i.e. 5

first create an array which contains 1 to 5 than a [] = {1, 2, 3, 4, 5}
Now try to generate a random number from 1 to 5 (here you are generating an index of the array) , lets suppose it generates 2 than replace last element to 2 . So now the array will be a[] = {1, 5, 3, 4} and decrement the index value.
now you will have to generate a random number from 1 to 4. Lets suppose 3 than swap 3 and last value. So array is {1, 5, 4}. Decrement the index i.e. now 3.

edited Nov 12 '13 at 00:29

answered Nov 12 '13 at 00:20

Trying

14,004
9
70
110

for the second approach, how are you making sure that there is on duplicated element in the 2nd columns ? – andre_lamothe Nov 12 '13 at 00:34
@AhmedSaleh above code always generates unique number from 1 to 5. No repetition at all. – Trying Nov 12 '13 at 00:37
they should be unique, but not to themselves, to the 2nd column. – andre_lamothe Nov 12 '13 at 00:40

score 0 · Accepted Answer · answered Nov 12 '13 at 00:48

I think this is a rather straight forward solution

    Random r = new Random();
    List<Integer> numbers = new ArrayList<>(Arrays.asList(new Integer[] {
            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }));

    Integer[] colOne = new Integer[] { 6, 5, 3 };
    numbers.removeAll(Arrays.asList(colOne));

    int notFoundInColOne = numbers.get(r.nextInt(numbers.size()));

Essentially we create our range, remove the elements in the range that are also in the column, then pick a random element from what remains of our range.

score 0 · Answer 3 · answered Nov 12 '13 at 04:26

0

I think this approach will work for you: For each number from 1 to 12, if the number is not in column 2 then add it to a list. While column 1 is not filled, randomly choose an item from the list and remove it, then add it to column 1.

answered Nov 12 '13 at 04:26

Duncan

984
10
20

score 0 · Answer 4 · answered Nov 12 '13 at 07:07

0

You can use these steps: 1. Create an array. 2. Fill it with minimum value to maximum value. 3. Suffle the array. Read array sequentially.

Use Fisher–Yates shuffle Algorithm for suffle

answered Nov 12 '13 at 07:07

dkumar

33
4

Fast way to generate random columns elements

4 Answers4