CODEWITHSUNDEEP
algorithmlanguage-agnosticpermutationcombinations
Raghav Sood
Raghav Sood

Reputation: 82563

All Possible Combinations from non uniform table, with only one value from each column

Background

In grade 11 in my school, we are required to take 4 subjects and English from a list of predefined subjects. Today, we were given a grid which helps us make our combo, such that you can only take one subject from each column.

The Grid

|    Economics     |   Maths  | Psychology/Politcal Science |                     English                      |     Geography    |
| Hindi/Psychology |  History |          Sociology          |                       Art                        | Elective English |
|      Maths       |  Account |          Commerce           |                    Economics                     |      English     |
|     English      |  Physics |          Chemistry          | Biology/Computer Applications/Mecahnical drawing |       Maths      |

The Problem

I'm trying to write a program to list out all possible legal combinations from this table. The rules are:

Now this would be a pretty simply task if it were a normal 4 by 5 matrix. However, [row 1, column 3], [row 2, column 1] and [row 4, column 4] contain more than one subject, out of which you can still pick only one. So any combination with any of those cells can be subdivided into more combinations.

I'm having trouble coming up with an algorithm for this. I'm not asking for free code, but instead help with the algorithm. I'm comfortable with most major languages (Java, JavaScript, PHP etc), and pseudo codes and flowcharts work too.

Upvotes: 2

Views: 438

Answers (3)

Shade
Shade

Reputation: 10011

This solution can, in theory, work for an infinite number of columns and an infinite and varying number of rows within the columns.

  1. Split the multi-subject rows into separate rows while filling the columns.
  2. Put the columns in an array and order it with the English-containing columns being first.
  3. Iterate the following while you still have English in any columns (we'll remove it one-by-one):
    1. Always take the first column. It contains English.
    2. Choose its English as the first element of all combinations in this iteration.
    3. Construct all combinations from the other columns recursively, taking care to eliminate duplicates. Doable, if you pass around your current combination.
    4. Remove the English from this column and sort the columns again (based on whether they have English or not).

This should get you all combinations that start with English and eliminate all duplicates.

EDIT: I implemented the solution above and it seems to work. Check it here - https://github.com/zupper/so-answers/tree/master/RaghavCombos

Upvotes: 4

Xantix
Xantix

Reputation: 3331

I would start by dealing with the cells with multiple values. We could convert the first column to the following list:

Economics
Hindi
Psychology
Maths
English

Since you could only choose one class in each column, this doesn't introduce any problems, and it can be done for each column.

Now, dealing with English is a little different. I'm going to refer to the different columns as periods. You know that the student must take English during 1st period, 4th period, or 5th period.

So, list all the combinations where English is selected in column 1. next, list all the combinations with English selected in column 4. and then list all the combinations with English selected in column 5.

You will need to decide whether or not a student may have English selected in more than one column. If so, you would need to deal with these seperately, so you don't double count things, like the following:

  • Combinations with English only in column 1
  • Combinations with English only in column 4
  • Combinations with English only in column 5
  • Combinations with English only in columns 1,4
  • Combinations with English only in columns 1,5
  • Combinations with English only in columns 4,5
  • Combinations with English only in columns 1,4,5

It does get a little complicated, but this way you don't overcount, and are able to list all combinations.

Upvotes: 1

slebetman
slebetman

Reputation: 113994

For all practical purposes, lines containing two subjects are essentially two lines. Therefore column 1 in the table actually contains 5 rows, not 4.

The first thing I'd do. If given such a dataset. Is to flatten the two subject lines. Something like this (pseudocode):

// Assuming:
grid = [
    [ economics, hindi/psychology, maths, english ] ,
    [
      // the rest is as per your table ...
    ],
]

foreach list grid {
    tmp = []
    while (list not empty) {
        item = list.pop()
        tmp.push(item.split('/'))
    }
    list = tmp
}

Then simply iterate each column and discard results that don't contain english or contains duplicates:

result = []

foreach item1 grid[0] {
  foreach item2 grid[1] {
    foreach item3 grid[2] {
      foreach item4 grid[3] {

        tmp = [item1,item2,item3,item4]

        if (not tmp.contains_duplicate && tmp.contains(english)) {
            result.push(tmp)
        } 
      }
    }
  }
}

The nested for loop is basically how you iterate over all combinations. You can add any conditional you want to filter out unwanted results.

Upvotes: 1

Related Questions