msjob99
BAN USER- 2of 2 votes
AnswersGiven a set of numbers from 1 to n squared, generate unique sub-sets consisting of n numbers such that each subset has one and only one matching number from any other sub-set
- msjob99 in United States
The max number of sub-sets is n squared + n
An example is as follows:
n = 3
n squared set = 1, 2, 3, 4, 5, 6, 7, 8, 9
sub-set 1 = 1, 2, 3
sub-set 2 = 1, 4, 7
sub-set 3 = 1, 5, 9
sub-set 4 = 1, 6, 8
sub-set 5 = 2, 5, 8
sub-set 6 = 2, 4, 9
sub-set 7 = 2, 6, 7
sub-set 8 = 3, 6, 9
sub-set 9 = 3, 5, 7
sub-set 10 = 3. 4, 8
sub-set 11 = 4, 5, 6
sub-set 12 = 7, 8, 9
Write the C++ algorithm that will work for any arbitrary integer value n. The n-squared set can be placed into any built in C++ data structure eg 2d array.| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm
Each subset does not have to match every other subset. Each subset must only be able to match at most 1 number from a given subset. ie. you will see that there are no other subsets where 7 and 8 are in the same subset or a 7 and 9 or an 8 and 9 other than in set 12.
The followup question is exactly what you're getting to:
Once you have the sub-sets described in this problem, then improve the algorithm to have one subset match exactly 1 number with every other subset.
RepDonnaWHale, Data Engineer at ADP
Hi, I am passionate writer with a BA in English from the Ohio State University.5+ years of experience writing ...
You are correct, however when you try it with a larger than 3x3 array, you will see that your algorithm no longer will get n^2 + n sets.
- msjob99 April 12, 2012