Number of integers where digits are not repeating.

Question

Number of integers where digits are not repeating.

Viewing 8 posts - 31 through 37 (of 37 total)

You must be logged in to reply to this topic. Login to reply

ben.brugman SSChampion Points: 13369 More actions · Answer 1

Phil Parkin - Thursday, March 2, 2017 12:06 PM
Here goes.
A non-negative integer, containing 'n' unique digits, with no leading zero, has the following number of results:
10!/(10-n)! - 9*8!/(10-n)!
Sum that, for n = 1 to 10, and add 1 for the special case (0) to get 8,877,691.

Bit different, but with the same result

A non-negative integer, containing 'n' unique digits, with no leading zero, has the following number of results:

9 * 9! / (9-n)!

Sum that, for n = 0 to 9, and add 1 for the special case (0) to get 8,877,691.

Three parts :
9 is the number of possibilities for the first position. (10 can be used if there is only one position).
C(9,n) is the number of combinations for the remainder. (n from 0 to 9)
P(n,n) or n! is the number of permutations of this set.

9 * C(9,n) * P(n,n) =
9 * 9! / ((9-n)! * n!) * n! = -- written out
9 * 9! / (9-n)! -- The division by n! cancelled out with the multiplier for n!

In the spreadsheat I used 10 for the number of posibilities in the first position if only one digit is used. (10 * 9! / (9-0)! = 10)

		combinations - permutations
First digit	Remaning digits		total
f	n	f*9!/(9-n)!
10	0	10	10
9	1	81	91
9	2	648	739
9	3	4536	5275
9	4	27216	32491
9	5	136080	168571
9	6	544320	712891
9	7	1632960	2345851
9	8	3265920	5611771
9	9	3265920	8877691

Thank you for your contribution, you were the first with this answer.
Ben

sgmunson

Group: General Forum Members
Points: 3860 Visits: 4033

Here's my code for this, and it runs in just 10 seconds on my Core i7 machine (2.9 GHz), 32 GB of RAM, SQL 2014:

This is extremely impressive. Still have to try out this code, but your result is beyond expectation. I was hoping for some faster code, but this is a real result.
I am still working on a method, that was before I saw this anwser. So tomorrow I will try that. Start with a single position in a string and recursively add another position to that, only if that does not conflict with the current content. Using the string compare function to detect 'conflicts'. I am going to use a string, because recursively I can not add extra fields from one to the next level.
But I do not expect to come close to your 10 seconds.

I am impressed.
Ben

Jeff Moden SSC Guru Points: 1004406 More actions · Answer 2

ben.brugman - Thursday, March 2, 2017 7:42 AM
--------- This is for fun only ---------
--------- This is for fun only (and for my education) ---------
--------- This is for fun only ---------
What is the possible number of non negative integers where none of the digits is repeating ?
7 is in the set.
22 is not in the set because the digit 2 is repeating.
Ben
Why ?
Two days a go I had to generate a list of 4 digit numbers, with some specific requirements, one of the requirements was that there were no repeating digits.
Started me wondering how many integers there are where non of the digits is repeating.
(Only non negative integers).
How to determine the number (count) using SQL only. (As elegant as possible)
And how to determine this set using SQL only. (As elegant as possible)
I used Excell to work out the number, but I would like to see some SQL which determines this number. Offcourse I can do the same calculation in SQL, but I do not 'consider' that elegant.
And I have build a script which can determine the posible number of integers of a specific length, I have not yet build an overall solution. And for the length of 7 positions this allready takes one and a half minute on my machine.
I sometimes see solutions in this forum which are 'inovative' to me, so, I though of asking this question here. As said this is for fun and education only. At the moment I have no application (or use) for this 'problem'.

Just to be sure on all of this... would the number 121 be included in the set or not. A lot of people are writing code to exclude it and I'd like to be sure.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

sgmunson SSC Guru Points: 110640 More actions · Answer 3

Jeff,

I've been reading through this topic from page 1, and I'm quite sure 121 would NOT be a member of the set, as it repeats a digit. All digits have to be unique, which was why I thought this exercise might be pretty easy to deal with. My code ran pretty quickly given the size of the cartesian product. before the WHERE clause kicks in. And the execution plan has a rather large number of Nested Loops, but none of them amounted to much more than a couple of percent of the total effort. I was amazed AND delighted... especially after seeing Ben be so happy with my solution. Of course, portions of my knowledge that allow me to come up with stuff like this are things I have you and much of the rest of the forum to thank for.

Steve (aka sgmunson) 🙂 🙂 🙂
Rent Servers for Income (picks and shovels strategy)

Matt Miller (4) SSC Guru Points: 124210 More actions · Answer 4

Why limit yourself only to Base(10)?

declare @base bigint; set @base=10;With digits as (
select top(@base) Row_number() over (order by (select null)) n from sys.all_columns),
recursecte as (
select cast(n as bigint) as digit, cast(case when @base<1 then 1 else @base-1 end as bigint) interim, cast(@base as bigint) dedupe
from digits where n=1
UNION ALL
select cast(n as bigint) as digit,cast(interim*(@base-(n-1)) as bigint),cast(interim*(@base-(n-1)) as bigint)+dedupe
from digits join recurseCTE on recursecte.digit+1 = digits.n
where digit<@base)
select * from recursecte where digit=@base

Explanation:
It's basically a modified deduped permutation formula. the main trick is to see that the length = 1 is where the exception is.At that point the math then just becomes:
If len=1 then permutations(len)=base --this helps to exclude leading zeroes
if len>1 then permutations(len)=(base-1) * fact(base-1)/fact(base-len) --you excluded the digit you picked at length 1 but put 0 back in.
If you sum all of the permutation for all possible lengths (i.e. for len=1 until len=base) then you have your answer

Recursive, but returns instantaneously on my machine. Note: the request was to count the options, not list them.

----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?

John Mitchell-245523 SSC Guru Points: 148809 More actions · Answer 5

ben.brugman - Thursday, March 2, 2017 4:08 PM
A non-negative integer, containing 'n' unique digits, with no leading zero, has the following number of results:
9 * 9! / (9-n)!
Sum that, for n = 0 to 9, and add 1 for the special case (0) to get 8,877,691.
Three parts :
9 is the number of possibilities for the first position. (10 can be used if there is only one position).
C(9,n) is the number of combinations for the remainder. (n from 0 to 9)
P(n,n) or n! is the number of permutations of this set.
9 * C(9,n) * P(n,n) =
9 * 9! / ((9-n)! * n!) * n! = -- written out
9 * 9! / (9-n)! -- The division by n! cancelled out with the multiplier for n!
In the spreadsheat I used 10 for the number of posibilities in the first position if only one digit is used. (10 * 9! / (9-0)! = 10)
combinations - permutations
First digit Remaning digits total
f n f*9!/(9-n)!
10 0 10 10
9 1 81 91
9 2 648 739
9 3 4536 5275
9 4 27216 32491
9 5 136080 168571
9 6 544320 712891
9 7 1632960 2345851
9 8 3265920 5611771
9 9 3265920 8877691
Thank you for your contribution, you were the first with this answer.
Ben
sgmunson

Group: General Forum Members
Points: 3860 Visits: 4033
Here's my code for this, and it runs in just 10 seconds on my Core i7 machine (2.9 GHz), 32 GB of RAM, SQL 2014:
This is extremely impressive. Still have to try out this code, but your result is beyond expectation. I was hoping for some faster code, but this is a real result.
I am still working on a method, that was before I saw this anwser. So tomorrow I will try that. Start with a single position in a string and recursively add another position to that, only if that does not conflict with the current content. Using the string compare function to detect 'conflicts'. I am going to use a string, because recursively I can not add extra fields from one to the next level.
But I do not expect to come close to your 10 seconds.
I am impressed.
Ben

Faster code? Here it is. It's based on what I posted yesterday, but even simpler, now that you've helpfully posted the formula. Runs in an instant.

WITH Factorials (Number, Factorial) AS ( SELECT 0, 1 UNION ALL SELECT 1, 1 UNION ALL SELECT 2, 2 UNION ALL SELECT 3, 6 UNION ALL SELECT 4, 24 UNION ALL SELECT 6, 720 UNION ALL SELECT 5, 120 UNION ALL SELECT 7, 5040 UNION ALL SELECT 8, 40320 UNION ALL SELECT 9, 362880 ) , Recursion AS ( SELECT 0 AS n , 10 AS Number , 10 AS Total UNION ALL SELECT n + 1 , 9 * 362880/f.Factorial , r.Total + 9 * 362880/f.Factorial FROM Recursion r JOIN Factorials f ON 8 - r.n = f.Number WHERE n <= 9 ) SELECT n , Number , Total FROM Recursion;

John

ben.brugman SSChampion Points: 13369 More actions · Answer 6

; WITH Digits0 AS (SELECT n FROM (VALUES ('0'),('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9'))x(n)) , Digits AS (SELECT CONVERT(VARCHAR(MAX),N) AS c, '%'+CONVERT(CHAR(1),N)+'%' s FROM digits0) , F AS (SELECT c AS r, 1 lng FROM digits UNION ALL SELECT R+c , lng+1 FROM F JOIN Digits ON r <> '0' AND r NOT LIKE s) SELECT COUNT(*) Tel, lng FROM F GROUP BY lng WITH ROLLUP ORDER BY TEL

------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------- -- Comments: -- -- Not as fast as sgmunson. (On my system around 32 secs). -- This routine 190 seconds. -- -- A bit shorter in code. -- Does not assume a limiting stringlength. -- Does not use a 'preprogrammed' number of recursions. -- Does not use any knowledge about factorials. -- Can produce the set of required numbers. -- On the set any selection can be done. (For checking for example). -- -- Workings: -- Digits contains all digits as a string and as a searchstring ('%n%'). -- -- Seed of the recursion is all string with a length of 1. (10 strings) -- The recursion part, add one character to the string for any char that does not exist yet. -- Exception the string '0' does not get added to. -- -------------------------------------------------------------------------------------------------------------------------

Remark.
As English is not my first language I used the word 'repeating', not realy realising that repeating is very often used for describing patterns. Maybe I should have used the word 'recurring'. Also I could have described that each digit is only allowed to appear once. (But that would have been a hint towards a solution, zo I avoided that).
Sorry for that confusion.

I have learned a great deal from this thread, Thanks:
Phil Parking who came with the first actual anwser, but used a different method to calculate the number of possible integers.
Luis Cazaras, who delivered the first script which could come up with an anwser. (But I have not run this to completing yet, because of the estimated time this consumes).
sgmunson, with an incredible fast script.

And all others which have contributed to the thread.

'Nice to see' is that most solutions at least take hours to 'form' themselves. The first brute force solution was overtaken with the fasted brute force solution. (I think) But the first anwser was a calculated solution.

This was a very usefull 'experience', because it made me understand some constructions a little bit better. It is this forum which does teach me a lot.

Next excercise for me is to use this code to come up with the number of patterns one can make from the 'Samsung' 9 dot security pattern. (With this as a starting point that is fairly easy, but I think this is for next week. 🙂 )

Everybody thanks for your contributions and educating me.
Ben

For a calculated solution.
See John Mitchells solution.

Or:
; WITH Fact AS (SELECT 0 n, convert(bigint,1) f UNION ALL SELECT n+1, f*(n+1) FROM Fact WHERE n < 20) , P AS (SELECT l,r FROM (VALUES (10,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9))x(r,l)) , S AS (SELECT P.l, (P.r * Fact1.f) / Fact2.f tel FROM P CROSS JOIN Fact Fact1 JOIN Fact Fact2 On Fact1.n=9 AND Fact2.n=9-l) SELECT l+1 as l, SUM(tel) tel FROM S GROUP BY l WITH ROLLUP ORDER BY tel;
--
-- Using the formula for the values of n from 0 to 9. The remainder after the first digit.
--
-- f * 9! / (9-n)!
-- f is the number of posible digits on the first position.
-- n is the remainder number of positions. (From 0 till 9).
--

-- Factorials are calculated within Fact.
-- P stands for positions, number of possible digits, and the remainder of the length.
-- In S the number of integers is calculated for each row in P.
-- The rollup gives to total number of possibilities

ben.brugman SSChampion Points: 13369 More actions · Answer 7

Matt Miller (#4) - Thursday, March 2, 2017 10:12 PM
Why limit yourself only to Base(10)?
code ........
Recursive, but returns instantaneously on my machine. Note: the request was to count the options, not list them.

Why limit yourself only to Base(10)?
A very valid question.
Most people think in Base 10, most 'code' systems requiring numeric codes are in base 10.
With the script bases above 12 will result in an arithmetec overflow, at least I would have expected the base to go up to 16 🙂

Yes the request was the number and it was not specified if this should be counted from actual rows or calculated in another way.
So your script does anwser the question. And what is very elegant about this script, it does not use a lot of operators. Although there are some repeats, only one multiply is used twice for each row and two subtracts are used twice for each row. Far less than the number of multiplications used when using the factorials. And even one subtract can be eliminated, if you want to reduce the number of operators.

(This is very similar how I started of in the spreadsheat, but wanting independend rows, reworked that to a solution using the factorials.)
Your solution in a spreadsheat requires far less operations (one subtraction, one multiply and one addition for each row), so I consider that superiour. Kudo's.

Initialy I skipped your posting, because the text is not displayed wel, it overlaps with itself.

Offcourse the solutions generating the sets with possibilities are hugely appreciated as wel. (This was asked furtheron in the first posting).

Thanks,
Ben

Matt Miller (4) SSC Guru Points: 124210 More actions · Answer 8

ben.brugman - Friday, March 3, 2017 8:53 AM
Matt Miller (#4) - Thursday, March 2, 2017 10:12 PM
Why limit yourself only to Base(10)?
code ........
Recursive, but returns instantaneously on my machine. Note: the request was to count the options, not list them.
Why limit yourself only to Base(10)?
A very valid question.
Most people think in Base 10, most 'code' systems requiring numeric codes are in base 10.
With the script bases above 12 will result in an arithmetec overflow, at least I would have expected the base to go up to 16 🙂
Yes the request was the number and it was not specified if this should be counted from actual rows or calculated in another way.
So your script does anwser the question. And what is very elegant about this script, it does not use a lot of operators. Although there are some repeats, only one multiply is used twice for each row and two subtracts are used twice for each row. Far less than the number of multiplications used when using the factorials. And even one subtract can be eliminated, if you want to reduce the number of operators.
(This is very similar how I started of in the spreadsheat, but wanting independend rows, reworked that to a solution using the factorials.)
Your solution in a spreadsheat requires far less operations (one subtraction, one multiply and one addition for each row), so I consider that superiour. Kudo's.
Initialy I skipped your posting, because the text is not displayed wel, it overlaps with itself.
Offcourse the solutions generating the sets with possibilities are hugely appreciated as wel. (This was asked furtheron in the first posting).
Thanks,
Ben

Yes - I forgot to cast things as bigint in the version I pasted. With Bigint (literally, do a find and replace from int to bigint and voila), it actually goes to base 16 (and higher).

and I don't know why the formatting got chunked up. I will admit I saw it fall outside of the script box, tried one or tw things, and then went to sleep :w00t:

update: it's fixed now - should be a lot easier to read!

----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?