Web Hosting Talk : Web Hosting Main Forums : Programming Discussion : all possible combinations or permutations

[Adam Hallett]

The problem is generating all possible combinations of the last 4 digits of a phone number. I've found much code that is combination or permutation generators, but all generate incomplete lists. Thoughts? Java,PHP,C,C++ is what I've tried so far as far as libraries, classes, etc go.

[tobiasly]

I'm not sure I understand your question, because it sounds like you just need a for() loop to count from 0 to 9999?

[Xeentech]

perl -e 'while(++$i < 999) { printf("<start of phone number>%4.4d ", $i - 1) }'

[innova]

No, you didnt understand his question.

0, 1, 2... are not 4-digit numbers. The problem is not quite as easy as it looks, but still pretty easy

One approach (pseudocode - should be easy to implement in the language of your choice):

For i in 0-9999
do
if number_of_digits($i) less than 4,
$i++ #advance to next number in series
else
echo $i && $i++ #echo and increment
done

You could even run two nested loops if you wanted to get all permutations of suffix (xxx-) and prefix (-yyyy). This would be horribly slow and I am sure there are better ways, lol.

[Xeentech]

I take it don't understand how printf works, and haven't even tried my code?

It will print "0000" though "9999". That's what the %4.d in the printf arg does. 0000 is a valid suffix for PSTN numbers, at least where I live (UK)

[tobiasly]

Originally Posted by innova

No, you didnt understand his question.

0, 1, 2... are not 4-digit numbers.

Sure they are. You just need to make sure they're formatted that way by zero-padding to 4 digits:
0000
0001
0002
...
9998
9999

That's it. Those are all the possible combinations of every 4-digit number.

PHP Code:

for($i=0; $i<=9999; $i++){
    printf("%04d\n", $i);
} 


[tobiasly]

Originally Posted by Xeentech

I take it don't understand how printf works, and haven't even tried my code?

I don't think you've tried it either, because it doesn't quite work.

"%4.4d" doesn't put in the leading zeros, at least on my version of PHP (tested on 5.2.0 and 5.2.1). Yes, I know every other programming language that uses printf works the way you wrote, but apparently PHP needs to be different...

http://us3.php.net/manual/en/function.sprintf.php

[Xeentech]

Who said anything about PHP, why does it have to be PHP?

perl -e 'while(++$i < 999) { printf("<start of phone number>%4.4d ", $i - 1) }'

Is what I suggested. You'll note at the start of the line it says perl.. Thats to suggest I tested it in perl. The Same would work in C and C++ that the OP said he had been testing with.

[Burhan]

If I remember my math right, there are 3,024 possible permutations for nnnn where n is {0,9}; and just with a cursory glance, I don't think any solutions provided here are right.

See this wiki entry for more information.

Neat problem, sounds like homework

[Xeentech]

How can 0000 though 9999 not be all the permutations, just as if you count to 100 you count all the numbers in between. There are 10000 permutations, including 0000 (which is valid).

[Burhan]

Because, what you are talking about is serial, not permutations.

Between 0 and 9, there are 10 possible combinations.

If you take a set of 3 numbers and want all possible permutations, at first you would think, oh wait, that's just 999 because that's the max you can go.

000
......
999

But, according to some weird math -- the actual number is 720 unique permutations.

Quoting Wikipedia:

In this section only, the traditional definition is used: a permutation is an ordered list without repetitions, perhaps missing some elements. The number of permutations of a sequence is:

n!/(n-r)!

where:

* r is the size of each permutation,
* n is the size of the sequence from which elements are permuted, and
* ! is the factorial operator.

For example, if we have a total of 10 elements, the integers {1, 2, ..., 10}, a permutation of three elements from this set is (5, 3, 4). In this case, n = 10 and r = 3. To find out how many unique sequences, such as the one previously, we can find, we need to calculate P(10,3) = 720.

An easier way to compute this is to take the first r numbers of n factorial; in this case: take the first 3 numbers in 10 factorial, so you would have 10 times 9 times 8, which equalls 720.

[Xeentech]

That may be the case if we weren't padding the number with 0s to make it four digits.

If you count from 0 to 9999 then no numbers are repeated and no possible combination is missed.

[Burhan]

Originally Posted by Xeentech

That may be the case if we weren't padding the number with 0s to make it four digits.

If you count from 0 to 9999 then no numbers are repeated and no possible combination is missed.

Now, you have figured out what is wrong with all the solutions posted here. Because they are going from the single digit 0 to 9999. They should be going from 0000 to 9999.

[Xeentech]

For the math impaired: 0000 == 0. And 0001 is the same as 1.

What do you think the difference is?

[tobiasly]

Fyrstrtr, you're making this way harder than you need to. Xeentech's solution is correct, except that it only counts to 999 instead of 9999. Digits in a phone number are just regular integers that are zero-padded.

It's neither a permutation nor a combination, because in both of those, you can't repeat digits. Which means that "1001" isn't a valid permutation of the digits 0-9, but it is a valid last 4 digits of a phone number.