Week 10: Exercises

1. All Sequences

Write a method sequences(int n, int k) that returns an enumeration of all possible sequences of n integers, each of which is in the range { 1 .. k }. Represent each sequence as a string such as "3 3 1 2".

For example,

foreach (string s in sequences(2, 3))
    WriteLine(s);

might print (in some order)

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

And

foreach (string s in sequences(3, 2))
    WriteLine(s);

might print (in some order)

1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

2. Combinations

Write a method combinations(int n, int k) that returns an enumeration of all k-element subsets of the set {1, 2, …, n}. Represent each subset as a string such as "2 4 7".

3. Combinations using Linked Lists

Conder this linked list class:

class Node<T> {
    public T val;
    public Node<T> next;
    
    public Node(T val, Node<T> next) {
        this.val = val; this.next = next;
    }
}

Write a method combinations<T>(Node<T> list, int k) that returns an enumeration of all k-element subsets of the given list. Represent each subset using a linked list.

4. Permutations

Write a method permutations(int n) that generates an enumeration of all permutations of the set {1, 2, …, n}. Represent permutations using strings.