Fuzzy algorithm for grouping data

Starting from permutations and combinations, I think we're interested in combinations:

For 30 topics, you would have the followng count of combinations for each size:

(In other words there are 30 combinations of size 1, and 435 combinations of size 2 (also 435 of size 28 as it turns out)).

1. 30
2. 435
3. 4060
4. 27405
5. 142506
6. 593775
7. 2035800
8. 5852925
9. 14307150
10. 30045015
11. 54627300
12. 86493225
13. 119759850
14. 145422675
15. 155117520
16. 145422675
17. 119759850
18. 86493225
19. 54627300
20. 30045015
21. 14307150
22. 5852925
23. 2035800
24. 593775
25. 142506
26. 27405
27. 4060
28. 435
29. 30
30. 1

I think you could generate each of the combinations for each size of combination from 1-30. You can google "generate all combinations", and, also, I have attached one that I whipped up below.

For each combination size, we might find the combinations, and find occurrences of them among students, and sort them by their count. You could have a cutoff of interest, keeping only the top some % for each size.

We can store each student's topic score with one bit. Thus, for 30 topics, we need 30 bits per student. On a 64-bit machine, we can store up to 64 bits in a single integer.

We can represent a combination also as an integer, whose bits are set to represent what elements are in the combination. In other words, a combination of size 6 is represented by an integer having exactly 6 of its bits set.

So, given a combination, we can test each of the ~200 students for match with a simple logical bitwise AND operation followed by a compare.

for ( var i = 0; i < 200; i++ )
    if ( (studentScores [i] & currentCombinaton) == currentCombination )
       // this combination matched for this student.

NOTE as written this is checking for success combinations not failure combinations, but that is easily reversed (using == 0 instead of == currentCombination).

So, that's a start.

I would think that you could do an analysis of combinations relative to each other, such as what popular combinations of size 4 or 5 are found in the popular combinations of size 16.

Below is a C# program I wrote that generates combinations of T/F values as bit mask. You could put that combo generator in a size loop, and use the above student occurrence loop for each such size.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication17
{
    class Program
    {
        static ulong NextCombination ( int outOf, ulong last )
        {
            int i;
            for ( i = 0; i < outOf; i++ )
            {
                if ( (last & (1UL << i)) != 0 )
                    break;
            }

            int j;
            for ( j = i + 1; j < outOf; j++ )
            {
                if ( (last & (1UL << j)) == 0 )
                    break;
            }

            // we alter the number by removing all the consecutive ones
            //  that occur followed by a zero (viewed from low order to high order)
            //  as in ...0111...
            // replace with a single 1
            //  as in ...1000... and set low bits to bits in a row, i.e.
            //  ...1000.....011

            int numberOfOnesInARowBeforeFirstZero = j - i;

            var onesMask = ((1UL << numberOfOnesInARowBeforeFirstZero) - 1) << i;
            last &= ~onesMask; // clear the series of one's

            last |= 1UL << j; // set the first zero bit after the ones in a row

            var lowOnesReplacement = (1UL << (numberOfOnesInARowBeforeFirstZero - 1)) - 1;
            last |= lowOnesReplacement; // set the lowest bits to make up for the cleared bits

            return last;
        }

        static void Main ( string [] args )
        {
            int comboSize = 3;
            int outOfSize = 30;

            int count = 1;

            ulong currentCombination = (1UL << comboSize) - 1;
            ulong lastCombination = currentCombination << (outOfSize - comboSize);
            System.Console.WriteLine ( "Last Combination for size " + comboSize + " is " + Convert.ToString ( (long) lastCombination, 2 ).PadLeft ( outOfSize, '0' ) );
            for ( ;; )
            {
                System.Console.WriteLine ( "Combination " + count + " is " + Convert.ToString ( (long) currentCombination, 2 ).PadLeft ( outOfSize, '0' ) );
                if ( currentCombination == lastCombination )
                    break;
                currentCombination = NextCombination ( outOfSize, currentCombination );
                count++;
            }
            System.Console.ReadLine ();
        }
    }
}

It would need to seek the largest possible subsets of topics, subject to matching a minimum number of students.

So you essentially have 2 criteria. Let's look at "largest possible subset" first:

This is brute force, unfortunately. In other words, you don't know the largest group until you've tallied all of the results. (Except you could optimize on very large datasets - but let's ignore that for now.)

So, you iterate over all topics and sum the votes. Then next, be sure that the votes exceed the "minimum".

At this point you have all topics that have sufficient votes. One optimization in this process is to recognize that if the topic with the fewest votes exceeds the total of all remaining votes, then you can stop. But, it's likely the brute force approach will be fast enough without optimization unless voting is in excess of millions.

Pseudo code might be:

 int topicVotes = 0;
 Array[Integer] topics = new Array[topics.size];
 for (i = 0; i < topics.size; i++) {
      for (j = 0; j < votes.size; j++) {
           if (votes[j] == true) topicVotes++;
      }
      if (topicVotes > minimum) topics[i] = topicVotes;
 }

This might not be the best way to implement this, but it should illustrate how to filter out the topics that don't meet the minimum requirement while emphasizing that brute force is required (in most cases) to guarantee that all topics meeting the minimum are included.