optimize random numbers b/w 1 to n w/o repetition

This is a discussion on optimize random numbers b/w 1 to n w/o repetition within the C++ Programming forums, part of the General Programming Boards category; Hi, I am writing this to be used as generating an initial random permutation from 1 to n out of ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    12

    Lightbulb optimize random numbers b/w 1 to n w/o repetition

    Hi,
    I am writing this to be used as generating an initial random permutation from 1 to n out of which a graph will be constructed on which the algorithm for the quadratic assignment problem will be used. Since the whole goal is time effeciency and better optimized code, how can i make this code more optimized and a little less lines of code

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <iostream.h>
    #include <time.h>
    
    
    int main() {
    
    	int test = 0,a = 0, i = 0,n = 0, k = 0, *perm;
    
    	printf("Enter value of n: ");
    	scanf("%d",&n);
    	printf("size of the permutation array is [%d]\n",n);
    	
    	perm = new int[n];
    	if(perm == NULL)
    		printf("Unable to assign memory to permutation array of size [%d]\n",n);
    	for (k = 0;k < n;k++)
    		perm[k] = 0;
    
    	srand(time(0));
    	while(i != n) {
    		a = 1 + (rand() % n);
    		if( a <= n && a >= 1){			
    			for (k = 0;k < n;k++){
    				if( a == perm[k])
    					test = 1;
    			} 
    			if (test != 1)
    			{
    				perm[i] = a;
    				i++;
    			}
    			else
    				test =0;
    			
    		}
    	}
    	for (k=0;k < n;k++)
    		printf("[%d]",perm[k]);
    	printf("\n");
    	
    	delete [] perm;
    	return 0;
    }

  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    101
    Hello,

    You can make an array of elements 1...n and then shuffle them to get a random premutation:
    Code:
    #include <vector>
    #include <algorithm>
    #include <iostream>
    
    int main()
    {
        const int N = 20;
        std::vector<int> vec(N);
        for(int i(1); i <= N; ++i) vec[i - 1] = i;
        std::random_shuffle(vec.begin(), vec.end());
        std::copy(vec.begin(), vec.end(),
            std::ostream_iterator<int>(std::cout, " "));
    }
    - lmov

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    12
    This works but it will always generate the same random permutation of numbers over the length of the vector. Do you know that random_shuffle call is being seeded to time or not. I think it is not. Is their any other function call like this that is seeded to time. I will try to look into the header file "algorithm.h" but if anybody else knows will appreciate

  4. #4
    Registered User
    Join Date
    Aug 2001
    Posts
    101
    random_shuffle uses rand by default so you can seed it with srand.
    - lmov

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. questions....so many questions about random numbers....
    By face_master in forum C++ Programming
    Replies: 2
    Last Post: 07-30-2009, 08:47 AM
  2. Doubts regarding random numbers generation
    By girish1026 in forum C Programming
    Replies: 9
    Last Post: 12-31-2008, 09:47 PM
  3. random numbers
    By mesmer in forum C Programming
    Replies: 4
    Last Post: 10-24-2008, 01:22 PM
  4. random numbers limit
    By HAssan in forum C Programming
    Replies: 9
    Last Post: 12-06-2005, 06:51 PM
  5. Generating 100k to 1 million unique random numbers
    By Ariod in forum C Programming
    Replies: 4
    Last Post: 08-26-2005, 12:59 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21