question about arrays and indicies

[accessuser1023]

all,

I have code that I can't wrap my head around. here it is:

    aPos(1) = aPos(1) + 1 
    For X = 1 To Len(sInput) - 1 
        If aPos(X) > Len(sInput) Then 
            aPos(X) = 1 
            aPos(X + 1) = aPos(X + 1) + 1
        End If
    Next X
    If aPos(Len(sInput)) > Len(sInput) Then Exit Do

this takes an input array of string and lists permutes. this is the first block of code. what I'm not following is what the last line is checking. I know in general, it's checking to see if there are more indicies captured from the array than there are for values in the array. If there's a mismatch it will exit. so in other words, "aPos(Len(sInput))" is looking for a 0 which indicates that the base 0 array indicies align with the number of array elements that are present.

but I'm not following the math and relation between indicies and the array values that it's evaluating.

anyone done this before? this was code pasted from the web.

any help appreciated. thank you.

 

[MarkK]

Understanding someone else's undocumented code is not trivial. Do you have some greater purpose or is this like a hobby, you download random and cryptic code and try to figure out what it does?

 

[accessuser1023]

Understanding someone else's undocumented code is not trivial. Do you have some greater purpose or is this like a hobby, you download random and cryptic code and try to figure out what it does?

of course it's not trivial. especially if it employs leveraging techniques like recursion or anything else. that's what this code does.

I'm working with vb6 and PHP at the moment for 2 different people and PHP is much more convenient in the fact that the function base is larger and some of the math is already built in. really what I'd like to do is take part of this code and use it in a PHP function. all of this code, if I posted it here, would output something like this for an input of '123':

• 1 2 3 12 13 21 23 31 32 123 132 213 231 312 321

what I'd like to do is dump the fully mutating portion of the code and output only unique combinations because the required output in PHP is a summation. so unique ordering isn't needed in that case as it is when you're listing full permutations like the example above.

make sense? and no, I'm not a hacker, in case that's the next question...thanks! they've already got the location anyway. (yikes!)

 

[MarkK]

No, I still don't get it. Are you trying to write code that given a set of items will return a list of all the permutations on those items? Also, would you be kind enough to distinguish permutations and combinations for me? I assume permutations don't respect the order of the elements and combinations do. What is a fully mutating portion of code?

I never thought you were a hacker, it's just you bothered to post, and I didn't, and still don't, understand your question.

The code you posted is incomplete. In one case it exits the loop, but what loop? If it's a function, how is it called?

Here's evidence I can program: http://www.access-programmers.co.uk/forums/showpost.php?p=1204886&postcount=7

Cheers,

 

[mdlueck]

I would do such with a custom collection class, which is taught to check for existence prior to adding to the collection to prevent duplicate values getting added to the collection.

Then allow the algorithm to just loop through how ever many possibilities might exist, add away, allow the duplicate prevention code in the collection class weed out the dupes.

Finally, enumerate through the collection.

 

[accessuser1023]

I know you can program, Lagbolt. I know your name here. Here's the full code (easy code is pseudo-written):

sub outputValues(strIn as string)

dim strOut() as string
strOut() = Permute(strIn)

For X = 0 To UBound(strOut)
    [I]cell [/I]= strOut(X)
        [I]increment cell[/I]
Next X

end sub

Public Function Permute(ByVal sInput As String) As String()

Dim aPos() As Long
Dim aString() As String
Dim lCounter As Long
Dim X As Long, Y As Long

ReDim aPos(1 To Len(sInput))

Do
    aPos(1) = aPos(1) + 1 [COLOR=SeaGreen]'move to second of indicies (skip first char).[/COLOR]
    
    For X = 1 To Len(sInput) - 1 [COLOR=SeaGreen]'for each of indicies except first[/COLOR]
        If aPos(X) > Len(sInput) Then[COLOR=SeaGreen] 'indicates that indicies value is within element range (do until outside of element range).[/COLOR]
            aPos(X) = 1 [COLOR=SeaGreen]'put each char in the string as seed (first) char to permute off of.[/COLOR]
            aPos(X + 1) = aPos(X + 1) + 1
        End If
    Next X

    If aPos(Len(sInput)) > Len(sInput) Then Exit Do

    For X = Len(sInput) To 2 Step -1
        If aPos(X) > 0 Then
            For Y = 1 To X - 1
                If aPos(X) = aPos(Y) Then GoTo Continue
            Next Y
        End If
    Next X

    ReDim Preserve aString(lCounter)

    For X = Len(sInput) To 1 Step -1
        If aPos(X) > 0 Then
            aString(lCounter) = aString(lCounter) & Mid(sInput, aPos(X), 1)
        End If
    Next X
    lCounter = lCounter + 1

Continue:
Loop

Permute = aString

End Function

The comments are what I'm writing down so I can follow it. And this function isn't calling itself either. But I guess you don't have to for this.

The eventual 'out' that I want in PHP is a summation of the elements that add up to another input value (not included here, but not needed in this example). There may be 0,1 or many output solutions, but the PHP function would hit return and exit as soon as the first one is found.

 

[accessuser1023]

sorry for the last original post, the comments near the end were not comprehendible. I changed them so they make sense now. thanks.

 

[MarkK]

fwiw, I still don't understand what you are seeking. The Permute() function works. Are you just looking to understand it better? Do you want to amend it somehow?
Cheers,

 

[accessuser1023]

Do you want to amend it somehow?

YES!! See previous post. Run it in excel and see an output. as you'll see, unique sequences are being output. but unique sequences aren't the same as unique combinations. the latter is what I want, so that involves a smaller list. stripping out the "dups" of the list, which would result in the same sum of the numbers.

for example, in the '123' example, the the part of the previous list that is:

• 132 213 231 312 321

would not be needed in the PHP function because the '123' output already satisfies what I want. only one of those listings would be needed because they all add up to the same sum. so I guess in other words, this needs to be modified to output unique sums instead of unique sequences of the input string. but don't be mistaken, the *combinations* of the input array elements must be output even if 2 or more of them may result in the same sum. so I guess technically speaking, we're not outputting unique *sums*. see what I'm getting at?

So here's an example output for an input of '123' that would be required for PHP (because all of the other original listings above would become redundant, as they would duplicate the same summation with the same set of elements, just having the elements listed in different order):

• 1 2 3 12 13 123

hopefully that makes sense! here, the output sums would be:

• 1 2 3 3 4 6

see it? are thanks so much!

again, from an engineering standpoint, here's a good representation:

[FONT=&quot]inputs: ([x, y, z], user-required sum = a). [/FONT]output: [indicies of elements whos sum = a]

 

[accessuser1023]

Lagbolt,

As a follow up to this whole thing, I only want assistance in trimming down the function in visual basic to give the outputs that are needed and not having to sift through what it currently outputs in terms of values. That's just too redundant. I can translate it to PHP without issue. syntax is irrelevant, that's just memorization. I don't have a problem with that.

thanks. hope you can help.

 

[MarkK]

So just to verify that I get it, you made an error here ...

• 1 2 3 12 13 123

... shouldn't it be ...

• 1 2 3 12 13 23 123

Is that correct? So you want all the combinations, not all the permutations?

If something occurs to me in a hurry I will post it. Cheers,

 

[accessuser1023]

So just to verify that I get it, you made an error here ...

• 1 2 3 12 13 123

... shouldn't it be ...

• 1 2 3 12 13 23 123

Is that correct? So you want all the combinations, not all the permutations?

If something occurs to me in a hurry I will post it. Cheers,

yes I did make an error there. thanks for catching that!!

yes I want all combinations and not all permutations. you are right, but keep in mind that is *not* always going to be rule. or rather, it shouldn't. because if it was "a rule" that you went by, you would have inputs such as (for example) the string '112' whereby the current code would produce the permutations:

• 1 1 2 11 12 11 12 21 21 112 121 112 121 211 211

but if we only wanted the combinations instead, it would then produce this:

• 1 2 11 12 112

and that's OK, but notice the redundancies in red. The outputs '2' and '11' are redundant because the summation of the values is the same (=2). So in short, a "unique combinations" list will work, but that still leaves the same amount of "cleanup" coding to be done to weed out redundancies like that, even if it is a shorter list of them. The redundancy check would still require the same iterative process so listing the "combinations" in all reality doesn't really satisfy all possible inputs. So I guess that's not the answer, but it's close. This is really a mathematics problem, it sure is tough to apply it to coding in any language!

thanks again!! you have been a great help so far. Cheers!

 

[accessuser1023]

Lagbolt,

Here's the answer in PHP:

$words = array(1,2,3,4);
$num = count($words);
//The total number of possible combinations
$total = pow(2, $num);
//Loop through each possible combination
for ($i = 0; $i < $total; $i++) {
         //For each combination check if each bit is set
for ($j = 0; $j < $total; $j++) {
         //Is bit $j set in $i?
         if (pow(2, $j) & $i) echo $words[$j] . ' ';    
}
echo '<br />';
}

so it's using bitwise to ask the machine if the current iteration through the nested loops is satisfying. What I don't understand here though, is why the array is being printed inside the 'J' loop when it would be undefined everytime 'J' was above 3 (which is the UBOUND() value for the array. you can't print out $words[4] because that's out of scope). But that would never happen would it? I know it wouldn't because it's impossible, but I don't understand WHY it's impossible. Just getting really low-level here. I'm a little tired and I'm having trouble thinking like a machine at the moment!

thoughts on this?