i have an idea of changing each row to decimal equilant so we have an array of size n each array element has logn bits, resetting each all bits except one everytime and checking for AND of all n array it should take maximum of O(logn)^n. improvements or ideas are welcome
surender On Sat, Jul 16, 2011 at 12:47 AM, Kunal Patil <[email protected]> wrote: > I agree with skript: Number of ways of doing this is n! > > One in the first row can be placed in n ways. > After one in first row has been placed, > we can place One in second row in n-1 ways and so on. > So total num of ways is n*(n-1)*...*1 = n! > > One possible solution to this problem can be coded as follows: > > Input: integer n > Output: different matrices satisfying given criteria > > > Create an array of integers 1 to n. > > do > { > // Omega( n! ) > For (i =0 to n-1) > // Omega(n) > print binary representation of (1 << arr[i] ) upto n bits // > Omega(n) > } while( Next_Permutation( arr, arr+n ) ); > > TC: Omega ( n! ) * Omega ( n ) * omega ( n ) > SC: O(n)...( I dunno [?] whether Next_permutation uses any extra space or > what, so i am not considering it... [?] ) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<1B2.png>>
<<324.png>>
