Question

Write a recursive algorithm in pseudo-code to compute the “power list” of a given list of integers. Assume that the List type has members:

int List.length returns the length of the list.
void List.push(T n) pushes an element n to the front of the list
T List.pop() pops an element from the front of the list.
List$$ List$$.concat(List$$ other) returns the concatenation of this list with other.

Explain in plain English the reasoning behind your algorithm.

Power Lists should be able to print ([],[1],[2], [3], [1,2], [1,3], [2,1], [2,3], [3,1],[3,2])
NOTE: [1,2] DOES NOT EQUAL [2,1]

Answer 1

The power list basically means we need to take all different combinations of numbers in the list and also consider all its permutations. So we will divide the task into two parts, getting all different combinations of numbers from the list of integers and then taking all the different permutation of that combination.

//the basic idea of generating all the combinations is to initially take an empty list at first
//and then pushing the numbers one in a recursion and calling for the next recursion using backtracking

list curr;   //for storing the current list of interger
list number; //given list of numbers

//curr is initially empty

integer index = -1;

//we will declare a recursive function here which will be called for generating all the
//combinations

powerList(index) 
    if index == number.lenght //if the index value is equal to length of the given list
        return;       //close the function here. you have permuted every number in the list
   
    //permute all the possible arrangements for the curr list 
    permute(curr,0,curr.lenght)
   
    //now we will append the ith number from the given list and call the recursion again
    for i = index+1, i< number.lenght ,i++
        curr.push(number[i])
        powerList(i)
        curr.pop()
   
    return;

//we have used the permute function so we will have to define that too
//this function is used to generate all the permutation of the combinations generated
//The logic of this permute function is to print everything if the first and the last index are same
// if they are not same swap the first number with the ith number and again call permutation on the next index
permutation(list curr, integer s, integer e) 
    if s == e
    print curr
       return;

    for i = s i <= e i++ 
        swap(curr[s], curr[i])
        permutation(curr, s + 1, e)
        swap(curr[s], curr[i])
    
     return;