CODEWITHSUNDEEP
algorithmdata-structuressubset
user3326034
user3326034

Reputation: 21

Algorithm/data structure for finding allowed subsets dynamically as selection is made

I am working on an application which shows a form for user input. The form has N sections with X radio buttons in each section. There is a subset of valid selection provided so as user works across sections, the buttons in other sections are enabled/disabled based on possibility of forming a valid subset.

For example: Section 1 has radio buttons for selection A, B and C Section 2 has buttons for selection 1, 2, 3 and 4 Section 3 has buttons for selection x, y, and z

Valid subsets are ({A,2,z},{B},{B,1,x},{C,4} User can start selection from any section, but I would have to disable buttons dynamically based on selection.

For the example above, if user starts with 2, I would only have A and z enabled (2 will also be enabled). I wont be able to use trie since it assumes order of input for prefix matching. Is there a data structure I could use for this?

Upvotes: 2

Views: 95

Answers (1)

NetVipeC
NetVipeC

Reputation: 4432

You could storage the enables radio button using a bitset like container. If you are using C++ you could use std::bitset if the size is known in compile time or boost::dynamic_bitset if it's not. If your are using other language most probably have a container like that already in their library, if not your could implemented by hand using a collection of int (as many int as needed according to the radio buttons).

It's only necessary to store one bitset by radio button (if this radio button is present in multiple valid subset, their bitset would be the bitwise-OR of all the subset that contained , indicating that when only this radio button is check the radio button indicated in the bitset are valid.

When you select any second radio button, you perform a bitwise-AND between the actual active radio button bitset and the bitset of active options that the newly checked radio button have (the precalculated). This mean that only would be active the radio buttons that are in at least one subset with all the previously selected radio button.

Example: Say that the radio button are: A, B, C, 1, 2, 3, 4, x, y and z it's the same in what section they are.

With the valid set: ({A,2,z},{B,2,z},{B},{B,1,x},{C,4}) with bitsets (one bit for every radio button):

A: 1000100001   B: 0101100101    C: 0010001000
1: 0101000100   2: 1100100001    3: 0000010000    4: 0010001000
x: 0101000100   y: 0000000010    z: 1100100001

This bitset could be precalculated when the valid subset are known and storage until they are not used more.

You would begin with 1111111111, all enable, you app would check this variable and enable or disable the radio button according.

When you select 2, the active radio button would be 1111111111 and 1100100001 = 1100100001, you update the radio button state (Only enabled A, B, 2 and z). If you then select A then 1100100001 and 1000100001 = 1000100001. (Only enabled A, 2 and z).

The bitset could be storage in an array or a list or array (one by section), as easier for programming.

Upvotes: 0

Related Questions