7

I am relatively new to programming. As the title suggests I require an algorithm that lets me get the same function of a variable nested loop. i.e.

for(..)
{ for(..){
for(..){....}
.
.
}}

The Number of nested loop will vary depending upon user input. What I am trying to achieve is finding all combinations of the numbers (10,9,8,7,6,5,4) Now I have read many. Either I dont understand them fully (I am new to programming world) or It doesnt serve my purpose. I need these combinations later in certain calculations and not just print all the combinations. One way, as I have learnt is to use recursion. I dont understand it fully. I tried to make a recursive function but failed miserably. This is what I want

10 10 10 
10 10 9
10 10 8
.
.
.
4  4  4 

The number can change (like 10 10 10 10 , 10 10 10 9 .. ) These combinations are to be stored in an array as I need them to manipulate later. Please keep it simple and comment.

Preferred language will be java. Any Language will do. A general algorithm is highly recommended. P.S. This is not a homework.

Thanks to amit. Here is the working code

def findcombinations(array,n,sol,tt=[]):
    if (n== 0):
        tt.append(sol[:])
        return
    for x in array:
        sol.append(x)
        findcombinations(array,n-1,sol,tt)        
        del sol[-1]
    return tt      

To call the function use print(findcombinations([1,2],3,[]))

2
  • Pedantically speaking, "10" isn't a digit. You may wish to reword that. Commented Feb 19, 2012 at 20:53
  • Sorry.. I will change that to numbers.. Thank You Commented Feb 24, 2012 at 6:12

3 Answers 3

5

Usually when you need "dynamic loops" - it is a strong indication you actually need recursion.

For example, finding all possible combinations of size n of digits in array [pseudo code]:

findCombinations(array,n,sol):
   if (sol.size == n): //stop condition for the recursion
      print sol
      return
   for each x in array:
      sol.append(x)
      findCombinations(array,n-1,sol) //recursive call
      sol.removeLast() //cleaning up environment

The above pseudo-code will find and print all sequences of length n made from elements from array [each element can appear more then once]

Sign up to request clarification or add additional context in comments.

14 Comments

I don't totally follow the dimensions of sol. Like I said I just dont want them to print but use all of them. (Sorry if I am missing something mainly due to the fact I am new to this). Also in java, can u increase the size of array dynamically ? (i.e. sol.append(x)) Also how to calculate n ? Should I calculate the no.of permutations beforehand ? Thank You.
Actually what is sol in this? :( Sorry for being such a noob.
I am sure am missing a lot. Please explain. I was wrong. Can you be language specific? I thought I could understand from a general representation. But i was mistaken. Thank You.
@Oasa: No apologies needed. sol holds the current permtuation [that you are currently working on]. It is initialized to an empty list when the algorithm starts, and it appends elements on the fly. There are many ways to implement this sol, but the simplest one is probably using an ArrayList. Note that ArrayList.add(element) appends the element to the end of the list
I understood the concept of ArrayList. Thanks a lot for that. Now sol is an array list I suppose. And initially it is zero.Is "array" is the entire permutation, I suppose. I still did not understand.
|
3

So you have one or more (well, maybe three or more) numbers, that should be able to range between 4 and 10? One way of doing that would be to have a simple counter and a function turning your counter into an array of numbers.

In pseudo-code:

counter_to_array(counter, positions):
  var array = new array(positions)

  for 0 <= i < positions:
    n = counter % 7
    counter = counter // 7  # INTEGER DIVISION
    array[i] = 4 + n

  return array

That is, your array is implicit in a counter and you can recreate it as needed. That may not be what you actually need and as written the arrays would go "4 4 4" "5 4 4" "6 4 4"..."10 10 9" "10 10 10", but changing that order is as simple as changing the order the array positions are filled.

Worked example: We want to generate a 4-element counter, the 11th.

  1. We create a 4-element array, called array.
  2. We loop through the array positions:
  3. We set array[0] to 8 (4 + (11 mod 7)))
  4. We set counter to 1 (11 div 7)
  5. We set array[1] to 5 (4 + (1 mod 7))
  6. We set counter to 0 (1 div 7)
  7. We set array[2] to 4
  8. We set array[3] to 4

So, the 11th array would be [8 5 4 4]

3 Comments

Suppose I call counter_to_array(10,4) It makes a new variable array with a dimension of 4; is that array[4] ? then a loop that goes from 0 to 4. and then n = 3; counter = 3; array[0]=3; array[1]=3; and so on. then i get an array full of 3s ? I am sure am missing a lot. Please explain. I was wrong. Can you be language specific? I thought I could understand from a general representation. But i was mistaken. I did not understand the purpose % 7 :( Thank You.
@oasa The counter is divided by 7 on each round, I added a worked example, I hope that helps.
I really could not follow. May be because of my noobness. Np. I found it from @amit 's answer. Thank you anyways. Always appreciated.
2

A solution that uses a while loop is given below. The code is in C++ and require # for the include and define statements

include <iostream>
define MAXROWS 9
define MAXVALUES 9

using namespace std;
char display[] = {'1','2','3','4','5','6','7','8','9'};

int main() {

int arrs[MAXROWS];  // represent the different variables in the for loops

bool status = false;

for (int r=0;r<MAXROWS;r++)
    arrs[r] = 0;  // Initialize values

while (!status) { 

    int total = 0;
    // calculate total for exit condition
    for (int r=0;r<MAXROWS;r++)
        total +=arrs[r];
    // test for exit condition
    if (total == (MAXVALUES-1)*MAXROWS)
        status = true;

    // printing
    for (int r=0;r<MAXROWS;r++)
        cout << display[arrs[r]]; // print(arrs[r])
    cout << endl;  // print(endline)

    // increment loop variables
        bool change = true;
    int r = MAXROWS-1;  // start from innermost loop
    while (change && r>=0) {
        // increment the innermost variable and check if spill overs
        if (++arrs[r] > MAXVALUES-1) {        
            arrs[r] = 0;  // reintialize loop variable
            // Change the upper variable by one
            // We need to increment the immediate upper level loop by one
            change = true;
        }
        else
            change = false; // Stop as there the upper levels of the loop are unaffected

        // We can perform any inner loop calculation here arrs[r]

        r=r-1;  // move to upper level of the loop

    }

}

[Link]http://www.codeproject.com/Tips/759707/Generating-dynamically-nested-loops It shows how a simple multiple nested loop can be converted to a dynamic one without using recursion.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.