Varying initializer in a 'for loop' in C++

Question

int i = 0;
for(; i<size-1; i++) {
    int temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
}

Here I started with the fist position of array. What if after the loop I need to execute the for loop again where the for loop starts with the next position of array.

Like for first for loop starts from: Array[0]

Second iteration: Array[1]

Third iteration: Array[2]

Example:

For array: 1 2 3 4 5

for i=0: 2 1 3 4 5, 2 3 1 4 5, 2 3 4 1 5, 2 3 4 5 1

for i=1: 1 3 2 4 5, 1 3 4 2 5, 1 3 4 5 2 so on.

Answer 1

You can nest loops inside each other, including the ability for the inner loop to access the iterator value of the outer loop. Thus:

for(int start = 0; start < size-1; start++) {
    for(int i = start; i < size-1; i++) {
        // Inner code on 'i'
    }
}

Would repeat your loop with an increasing start value, thus repeating with a higher initial value for i until you're gone through your list.

Answer 2

Suppose you have a routine to generate all possible permutations of the array elements for a given length n. Suppose the routine, after processing all n! permutations, leaves the n items of the array in their initial order.

Question: how can we build a routine to make all possible permutations of an array with (n+1) elements?

Answer:
Generate all permutations of the initial n elements, each time process the whole array; this way we have processed all n! permutations with the same last item.
Now, swap the (n+1)-st item with one of those n and repeat permuting n elements – we get another n! permutations with a new last item.
The n elements are left in their previous order, so put that last item back into its initial place and choose another one to put at the end of an array. Reiterate permuting n items.
And so on.

Remember, after each call the routine leaves the n-items array in its initial order. To retain this property at n+1 we need to make sure the same element gets finally placed at the end of an array after the (n+1)-st iteration of n! permutations.

This is how you can do that:

void ProcessAllPermutations(int arr[], int arrLen, int permLen)
{
    if(permLen == 1)
        ProcessThePermutation(arr, arrLen);         // print the permutation
    else
    {
        int lastpos = permLen - 1;                  // last item position for swaps

        for(int pos = lastpos; pos >= 0; pos--)     // pos of item to swap with the last
        {
            swap(arr[pos], arr[lastpos]);           // put the chosen item at the end
            ProcessAllPermutations(arr, arrLen, permLen - 1);
            swap(arr[pos], arr[lastpos]);           // put the chosen item back at pos
        }
    }
}

and here is an example of the routine running: https://ideone.com/sXp35O

Note, however, that this approach is highly ineffective:

1. It may work in a reasonable time for very small input size only. The number of permutations is a factorial function of the array length, and it grows faster than exponentially, which makes really BIG number of tests.
2. The routine has no short return. Even if the first or second permutation is the correct result, the routine will perform all the rest of n! unnecessary tests, too. Of course one can add a return path to break iteration, but that would make the code somewhat ugly. And it would bring no significant gain, because the routine will have to make n!/2 test on average.
3. Each generated permutation appears deep in the last level of the recursion. Testing for a correct result requires making a call to ProcessThePermutation from within ProcessAllPermutations, so it is difficult to replace the callee with some other function. The caller function must be modified each time you need another method of testing / procesing / whatever. Or one would have to provide a pointer to a processing function (a 'callback') and push it down through all the recursion, down to the place where the call will happen. This might be done indirectly by a virtual function in some context object, so it would look quite nice – but the overhead of passing additional data down the recursive calls can not be avoided.
4. The routine has yet another interesting property: it does not rely on the data values. Elements of the array are never compared. This may sometimes be an advantage: the routine can permute any kind of objects, even if they are not comparable. On the other hand it can not detect duplicates, so in case of equal items it will make repeated results. In a degenerate case of all n equal items the result will be n! equal sequences.

So if you ask how to generate all permutations to detect a sorted one, I must answer: DON'T.
Do learn effective sorting algorithms instead.