list-of-permutations.md

Problem Set: Lists of Permutations

Problem Description

You are tasked with writing a function joinAll(lls) which takes in a list of lists of strings and returns every permutation of elements from those lists, joined together with underscores (_).

Requirements:

1. The input is a list of lists of strings (e.g., [ ["a","b"], ["c"], ["d","e"] ]).
2. Each output string should be formed by picking exactly one element from each list in order, then joining them with underscores.
3. You may assume none of the sublists are empty.
4. The order of the final list does not matter (permutation order is not enforced).

---

Example Cases

Example 1

joinAll([ ["a","b","c"], ["d"], ["e", "f"] ])

Output:

["a_d_e", "a_d_f", "b_d_e", "b_d_f", "c_d_e", "c_d_f"]

Example 2

joinAll([ ["u", "v", "c"], ["w", "x"] ])

Output:

["u_w", "u_x", "v_w", "v_x", "c_w", "c_x"]

Example 3

joinAll([
    ["facebook", "google"],
    ["impressions", "clicks", "conversions", "combined"],
    ["report.pdf"]
])

Output:

[
  "facebook_impressions_report.pdf",
  "google_impressions_report.pdf",
  "facebook_clicks_report.pdf",
  "google_clicks_report.pdf",
  "facebook_conversions_report.pdf",
  "google_conversions_report.pdf",
  "facebook_combined_report.pdf",
  "google_combined_report.pdf"
]

---

Common Questions & Answers

1. Do I need to sort the results?

No. The order of the output list does not matter. As long as all valid permutations are included, your solution is correct.

---

2. Can a sublist contain only one element?

Yes. For example, [ ["x"], ["y", "z"] ] should return ["x_y", "x_z"]. The requirement only states that sublists cannot be empty.

---

3. What if all sublists contain only one element?

In that case, there is only one possible output. For example:

joinAll([ ["hello"], ["world"] ])
# Output: ["hello_world"]

---

4. How should I implement it?

This problem can be solved using:

• Recursion (building combinations step by step).
• Iteration with Cartesian product (itertools.product).

For example, using itertools.product:

from itertools import product

def joinAll(lls):
    return ["_".join(p) for p in product(*lls)]

---

5. What is the time complexity?

If each list has n elements and there are k lists, the total number of outputs will be the product of all list sizes. In the worst case:

O(n^k)

This is expected since we must enumerate all possible permutations.

---

Extensions / Variations

1. Custom Separator: Modify the function to accept a separator argument (e.g., joinAll(lls, sep="-")).
2. Empty List Handling: Extend to gracefully handle an empty sublist (return an empty result).
3. Filtering: Allow filtering combinations based on rules (e.g., exclude certain words).

---

Key Takeaways

• This problem introduces the idea of Cartesian products of lists.
• It's a practical example of how permutations/combinations are useful in data generation (e.g., generating filenames, testing cases, report combinations).
• Python’s built-in tools (itertools.product) make solving these problems concise and efficient.