How to write program to generate the following pattern?

Question

You can use recursion, loops, vectors or strings doesn't matter.

Given an input N will generate N lines of the pattern.

1
2
1 2
3
1 3
1 2 3
2 3
4
1 4
1 2 4
1 3 4
1 2 3 4
2 4
2 3 4
3 4
5

Edit: I figured out how to do it doing a pre-calculation. It is possible to do it iteratively one step at a time?

void per(vector<int> v, int value) {

    cout << v;
    if (v.size() == value) {
        return;
    }

    if(v.back() < value && v.size() < value) {
        vector<int> modified(v);
        for(int i = 0; i < modified.size(); i++) {
            modified[i] += 1;
        }
        per(modified, value);
    }

    if(v.back() < value && v.size() < value) {
        // for(int i = 0; i < value; i++) {
        vector<int> modified(v);
        modified.push_back(modified.back() + 1);
        per(modified, value);
    }


}

How do you think about such a recursive algorithm. I tried to draw a tree of the output but get suck. Maybe such problem doesn't fit well with recursion. It seems like it should be recursive and there is a smallest subset of the problem contained within.

Answer 1

You don't need to recursion for that,

Lets say we have an input n: 3, We need to create an array of 1..n = 1,2,3;

Where output should be:

1
2   12
3   13   23   123

function createPowerSet(n) {
    let res = [];
    for (let i = 1; i <= n; i++) {
        res.push([i])
        let len = res.length - 1;
        for (let j = 0; j < len; j++)
            res.push(res[j].concat(i))
    }
    return res
}
console.log(createPowerSet(4))

Answer 2

There is an iterative solution that involves, at iteration i, going through the previously added patterns that start with j, where j goes from 1 to i-1, and adding i.

Here's some Java code to illustrate:

static List<String> pattern(int n)
{
    List<String> res = new ArrayList<>();
    
    for(int i=1; i<n; i++)
    {
        res.add(String.valueOf(i));
        
        for(int j=1; j<i; j++)
        {
            int size = res.size();
            for(int k=0; k<size; k++)
                if(res.get(k).equals(String.valueOf(j)) || 
                        res.get(k).startsWith(String.valueOf(j) + " "))
                {
                    res.add(res.get(k) + " " + i);
                }
        }
    }
    return res;
}

Test:

for(String s : pattern(5)) System.out.println(s);       

Output:

1
2
1 2
3
1 3
1 2 3
2 3
4
1 4
1 2 4
1 3 4
1 2 3 4
2 4
2 3 4
3 4

There may be a cleverer approach involving recursion that avoids having to iterate through the previously added patterns and checking the first character, but I'm yet to see it.

EDIT:

Note the original version above had a problem once numbers start getting into multiple digits - e.g. startsWith(1) starts matching 10. I've updated the code to resolve this.

After playing around for a while I did manage to come up with a solution that I find more satisfying, which uses a combination of iteration and recursion to generate the list of entries at each given level. But it's not exactly simple.

static List<String> pattern(int n)
{
    List<String> res = new ArrayList<>();
    
    for(int i=1; i<=n; i++)
    {
        res.add(String.valueOf(i));
        
        for(int j=1; j<i; j++)              
            for(String s : list(i-1, j)) 
                res.add(String.format("%s %d", s, i));
    }
    
    return res;
}

static List<String> list(int i, int j)
{
    if(i == j) 
        return new ArrayList<>(Arrays.asList(String.valueOf(j)));
                    
    List<String> a = list(i-1, j);      
    for(int k=0, s=a.size(); k<s; k++) 
        a.add(String.format("%s %d", a.get(k), i));
    return a;
}

And a Javascript version.

function list(i, j) {
    if(i === j) return [j];
  
  let a = list(i-1, j);
  a.forEach(s => a.push(s + ' ' + i));
  return a;
}

function gen(n) {
    let res = []
  
  for(let i=1; i<=n; i++) {
    res.push(i.toString());
    for(let j=1; j<i; j++) {
      list(i-1, j).forEach(s => res.push(s + ' ' + i));
    }
  }
    
  return res
}

gen(4).forEach(_ => console.log(_));