LebGeeks

arithma

Member

[Exercise]Circular Equivalence Sets on Array

Given any array of n elements, and a integer number k (positive or negative).
Starting at index 0 for the first element and going through the array with k increments and wrapping around the array, the elements are deemed equivalent (or belonging to the same set).
How many sets are there for each (n, k) pair?

Note: Any equivalent formulation could work, especially for indexing starting with 1 where you have to be careful about the wrap around.

(n=2, k=0) = 2 sets

(n=2, k=1) = 1 set

(n=2, k=2) = 2 sets

(n=10, k=2) = 2 sets
0 1 2 3 4 5 6 7 8 9

(n=10, k=5) = 5 sets
0 1 2 3 4 5 6 7 8 9

(n=11, k=2) = 1 set

Last edited by arithma (October 17 2010)

mesa177

Member

Re: [Exercise]Circular Equivalence Sets on Array

How about when k is negative? Does it act like the negative shift key on the rotate array problem? i.e. do we start the indexing at the end of the array and then work our way up?

For a positive k and the number of sets denoted by the variable setNum: (the jist of the program, I'll post the entire code when you give me the heads up about a negative k)

if (k > length(array))
   setNum = 1; % All entries on the array belong to the same set
elseif mod(length(array),k) % mod is modulus for those who are not familiar with Matlab
       setNum = mod(length(array),k);
else
       setNum = k;
end

Last edited by mesa177 (October 17 2010)

Georges

Member

Re: [Exercise]Circular Equivalence Sets on Array

Calculating the number of sets obeys this formula:

nmbOfSets =  ( (n-1)%k ) + 1.

ex: For n = 10 and k = 2,
nmb = ((10-1)%2) + 1 = 2 sets.

Console.Write("Please enter the size of the array: n = ");
int n = Convert.ToInt32(Console.ReadLine());

Console.Write("Please enter the number k: k = ");
int k = Convert.ToInt32(Console.ReadLine());

int nmbOfSets = ((n - 1) % k) + 1;
Console.WriteLine("The number of sets is: {0}", nmbOfSets);

Console.ReadKey();

Last edited by Georges Raad (October 17 2010)

mesa177

Member

Re: [Exercise]Circular Equivalence Sets on Array

Calculating the number of sets obeys this formula:

nmbOfSets =  ( (n-1)%k ) + 1.

this formula doesn't apply when k > n where in this case all the entries belong to the same set

modify the code to resemble this then:

if (k > length(array))
   setNum = 1; % All entries on the array belong to the same set
else
   setNum = mod(length(array)-1,k)+1;
end

Georges

Member

Re: [Exercise]Circular Equivalence Sets on Array

Calculating the number of sets obeys this formula:

nmbOfSets =  ( (n-1)%k ) + 1.

this formula doesn't apply when k > n where in this case all the entries belong to the same set

I didn't know that K > N is possible.

I also have another question, in the case of n = 7, and k = 3.
Set 1: 1-4-7
set 2: 2-5
set 3: 3-6.

Do we count these as 3 sets since they have different sizes. Or 1 set since there's no other set of the same length.

mesa177

Member

Re: [Exercise]Circular Equivalence Sets on Array

I didn't know that K > N is possible.

I also have another question, in the case of n = 7, and k = 3.
Set 1: 1-4-7
set 2: 2-5
set 3: 3-6.

Do we count these as 3 sets since they have different sizes. Or 1 set since there's no other set of the same length.

Since wrap around is possible, then I think that yes, k can be greater than n.

[Edit/] Oops, my bad!! Yes, indeed, they do form one set since during the wrap around set 2 and set 3 become equivalent to set 1:

before wrap around:

set 1: 1-4-7
set 2: 2-5
set 3: 3-6

after 1st wrap around:
set 1: 1-4-7 = set 2: 2-5 since entry 1 on the array becomes a member of set 2 when entry 7 is considered a member of set 1 (k = 3, if entry 7 is the first count, the wrap around takes care of the second and third counts by reassigning entries 1 and 2 in the array to their new sets 2 and 3 respectively)
set 1 = set 2: 1-2-4-5-7
similary set 2: 2-5 = set 3: 3-6 => set 2 = set 3: 2-3-4-5 but set 1 = set 2 => set 1 = set 2 = set 3 = all entries

Last edited by mesa177 (October 18 2010)

arithma

Member

Re: [Exercise]Circular Equivalence Sets on Array

I didn't know that K > N is possible.

I also have another question, in the case of n = 7, and k = 3.
Set 1: 1-4-7
set 2: 2-5
set 3: 3-6.

Do we count these as 3 sets since they have different sizes. Or 1 set since there's no other set of the same length.

This is similar to the last example (n=11, k=2) which I put purposely to make this point clear. In your example, (n=7, k=3) the number of sets is again 1.

This info is already included in my definition of the problem in this sentence particularly:

Given any array of n elements, and a integer number k (positive or negative).
Starting at index 0 for the first element and going through the array with k increments and wrapping around the array, the elements are deemed equivalent (or belonging to the same set).

Last edited by arithma (October 17 2010)

arithma

Member

Re: [Exercise]Circular Equivalence Sets on Array

*** SPOILER ALERT ***
The solution for this exercise is:

        static int foobar(int n, int k)
        {
            if (k <= 1) return 1;
            if (n == k) return n;
            return foobar(k, k - (n % k));
        }

        static void Main(string[] args)
        {
            Console.WriteLine("{0}", foobar(11, 2));
            Console.WriteLine("{0}", foobar(10, 2));
            Console.WriteLine("{0}", foobar(10, 3));
            Console.WriteLine("{0}", foobar(10, 5));
        }
}

arithma

Member

Re: [Exercise]Circular Equivalence Sets on Array

I was thinking about this function and I figured it's the same as having the recursive part as:

foobar(k, n % k)

This is code for getting out the Greatest Common Divisor. I was toying around with that concept for this kind of problem and the rotation, and now I can see where they click exactly. All I have to do is think it through again while being awake for more insight. We can probably optimize out the function by smartly picking out either n%k or k-n%k.

Joe

Member

Re: [Exercise]Circular Equivalence Sets on Array

This code will generate the different sets created:

def gcd(a, b):
    return max(x for x in range(1, min(a, b) + 1) if a % x == 0 and b % x == 0)

def get_one(x, y): return y

def foo(k, n):
    for i in itertools.groupby(sorted(((x, x%gcd(k, n)) for x in range(1, n+1)), key=get_one, key=get_one):
       print(" ".join(str(x) for x, y in i[1]))

For instance for (10, 2):

2 4 6 8 10
1 3 5 7 9

The gcd() function has been singled out for clarity. If anyone wonders how it works, I'd gladly rewrite it more intelligibly.