Generating List with Variable Entries/Arguments

Question

This question is similar to Question i had asked before.

Suppose a library.

The library has many of Books(say B(1 to n)). (n =number of Books)

Each book can have many Chapters (say C(1 to k)) . (k= number of Chapters)

Every Chapter can have number of Lessons (say L(1 to j)) .. (j = number of Lessons)

Every Lessons can have number of Topics (say T(1 to i)) .. (i = number of Topics ) ... ...

Now suppose if I want to create a list such that it has "all" entries like

Book 1 Chapter 1 Lesson 1 Topic 1 ...    

Book 1 Chapter 1 Lesson 1 Topic 2 ...  

Book 1 Chapter 1 Lesson 1 Topic 3 ...  

Book 2 Chapter 1 Lesson 1 Topic 1 ...

Book 2 Chapter 1 Lesson 1 Topic 2 ...

Book 2 Chapter 1 Lesson 1 Topic 3 ...

Book 2 Chapter 1 Lesson 1 Topic 4 ...

Book 2 Chapter 2 Lesson 1 Topic 1 ...

Book 2 Chapter 2 Lesson 1 Topic 2 ...

Book 2 Chapter 2 Lesson 1 Topic 3 ...
.....

Book (x1) Chapter (x2) Lesson (x3) Topic (x4) ... 


  where  1 <= x1 <= n, 1 <= x2 <= k, 1<= x3 <= j, 1< = x4 < = i

(Above example shows "Book 1" with 1 chapter 1 lesson 3 topics and "Book 2" with 2 chapters with "lesson 1" and 4 topics in chapter 1 and "lesson 1" and 3 topics in chapter 2. ) How can this list be efficiently generated?

Also, the entry "Book (x1) Chapter (x2) Lesson (x3) Topic (x4)" is not limited to Topic (4 variables).
It can vary too. Grow or shrink .
eg: Topics can have Questions,Questions can have Sub Questions. (based on user selection.)

Note: This is purely academic

Does this problem fall in the NP class of problems?

Any programming language ..algorithm :)

Thanks All

What's different about this question than your previous question? Are you trying to generate all possible combinations (if so, isn't this a duplicate) or simply enumerate those combinations that do exist in your object graph? — Winston Smith, Jul 15 '10 at 10:44
i guess not that much different but a variation of the same. this problem could be seen as given {a(i),b(j),c(k)} combining b(j) with all c(k) (where numbers of c's is different for every b)and then combining result with 'a(i)'(for every a(i) b's and c's change.) .. something similar. — Amitd, Jul 15 '10 at 11:05
If it is a really `code-golf`, make the question Community-Wiki. Otherwise, remove that tag. — kennytm, Jul 15 '10 at 11:08
You basically have an array of names and an array of numbers. If you want to generate a list you can easily loop through them recursively. The efficiency will depend on how you store/print the results. Same thing with querying the results (relational-style). — Jaroslav Jandek, Jul 15 '10 at 11:22

score 1 · Answer 1 · answered Jul 15 '10 at 10:43

This is a very common situation, addressed by both the Relational Db model and, for example, XML.

Datastructures cannot be NP problems, but a algorithm applied to your library might be.

If you make the number of levels variable, it will require some meta-programming.

score 1 · Answer 2 · edited Jan 18 '23 at 11:22

Does this problem fall in the NP class of problems?

No, but generating all combinations has exponential time complexity in the depth of the section system (book-chapter-etc).

If you you have a way of determining if the current structure (e.g. chapter) should have children, you can do the following:

// The int value is the number of children
Tuple<string, int> GetChildStructure(string parentStructure) {
    if(parentStructure == "Library") return new Tuple<string, int>("Book", 3);
    if(parentStructure == "Book") return new Tuple<string, int>("Chapter", 2);
    // ...
    // You can get these from a config file/DB/etc
    return null;
}

void BuildStructure(Structure parent) {
   var childStruct = GetChildStructure(parent.StructName);
   if(childStruct != null) {
      for(int i=1; i <= childStruct.Item2; i++) {
         Structure child = new Structure(childStruct.Item1,  i);
         BuildStructure(child);
      }
   }
}

void Main() {
    var lib = new Structure("Library", 1);
    BuildStructure(lib);
}

You should also check this post out.

Generating List with Variable Entries/Arguments

2 Answers2