While solving I came up with an algorithm, but don't know the permutation and combinations to proceed further.↵
The algorithm is as follows:↵
↵
1) Input the numbers in a vector "v"↵
↵
2) Make a vector "primes" consisting of the prime numbers using Sieve of Eratosthenes.↵
↵
3) For every element in v, divide it by all primes smaller than it (if divisible).↵
↵
4) Sort it↵
↵
5) We will now have vector consisting of (1,1,1,1,2,2,2,3,3,5,5,6,6,6,7 ... types) i.e. all numbers except of perfect squares ↵
(1 will be there)↵
Now for the part I could not solve :↵
↵
6)↵
I want to arrange this vector thus formed of length n in such a manner that no 1's appear together, no 2's appear together, no 3's appear together ...etc.↵
For example, the given case :↵
{1,4,2}↵
after step 3:↵
{1,1,2}↵
after step 4↵
{1,1,2} (since already sorted)↵
after step 5↵
{1,2,1} is the valid arrays.↵
↵
7) I have to multiply this by a certain number but let's leave this for now.↵
↵
How can I solve the part 6).. ?
The algorithm is as follows:↵
↵
1) Input the numbers in a vector "v"↵
↵
2) Make a vector "primes" consisting of the prime numbers using Sieve of Eratosthenes.↵
↵
3) For every element in v, divide it by all primes smaller than it (if divisible).↵
↵
4) Sort it↵
↵
5) We will now have vector consisting of (1,1,1,1,2,2,2,3,3,5,5,6,6,6,7 ... types) i.e. all numbers except of perfect squares ↵
(1 will be there)↵
Now for the part I could not solve :↵
↵
6)↵
I want to arrange this vector thus formed of length n in such a manner that no 1's appear together, no 2's appear together, no 3's appear together ...etc.↵
For example, the given case :↵
{1,4,2}↵
after step 3:↵
{1,1,2}↵
after step 4↵
{1,1,2} (since already sorted)↵
after step 5↵
{1,2,1} is the valid arrays.↵
↵
7) I have to multiply this by a certain number but let's leave this for now.↵
↵
How can I solve the part 6).. ?