Number of integers where digits are not repeating.
-
--------- 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.Edit: (20170303 15:42 my local time):
the number 123452 is not in the set because the digit 2 is repeated.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'.
-
I think we need a few more parameters ...
As the set of integers is unbounded, the answer is an infinite number.
But, if you are saying, how many positive integers (ie, Natural Numbers) of length 'n' are there, which do not contain any coincident identical digits, I think it's more or less clear. You probably have to rule in or out leading zeros too.
The absence of evidence is not evidence of absence.
Martin ReesYou can lead a horse to water, but a pencil must be lead.
Stan Laurel - Phil Parkin - Thursday, March 2, 2017 7:53 AM
3, 03,003, 0003 are all the same integer to me. So as far as I know leading zero's is something from the representation, not some 'attribute' of the integer itself.
And the 'other' condition of non repeating, I mean that a digit should not occure twice or more in the integer, so the number 123452 is not in the set because the digit 2 is repeated. So I do not think more parameters are needed. Sorry that this was not clear.
Integers of any length are allowed as long as digits do not get repeated.Ben
- ben.brugman - Thursday, March 2, 2017 8:00 AM
OK, I misunderstood what you meant by repeating. Interesting problem.
The absence of evidence is not evidence of absence.
Martin ReesYou can lead a horse to water, but a pencil must be lead.
Stan Laurel -
Something like this?
-- Fixed length, 4 in this caseWITH Digits(N) AS (
SELECT N
FROM (VALUES('0'),('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9')) D(N)
)
SELECT d1.N+d2.N+d3.N+d4.N AS N
FROM Digits d1
INNER JOIN Digits d2 ON d2.N NOT IN (d1.N)
INNER JOIN Digits d3 ON d3.N NOT IN (d1.N,d2.N)
INNER JOIN Digits d4 ON d4.N NOT IN (d1.N,d2.N,D3.N)
ORDER BY N;-- Variable length
DECLARE @MaxLen INT = 4;WITH Digits(N) AS (
SELECT N
FROM (VALUES('0'),('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9')) D(N)
),
Recur AS (
SELECT CAST(N AS VARCHAR(20)) AS N
FROM DigitsUNION ALL
SELECT CAST(r.N + d.N AS VARCHAR(20)) AS N
FROM Recur r
INNER JOIN Digits d ON CHARINDEX(d.N,r.n) = 0
WHERE LEN(r.N)+1 <= @MaxLen
)
SELECT * FROM Recur
ORDER BY LEN(N),N;____________________________________________________
Deja View - The strange feeling that somewhere, sometime you've optimised this query before
How to get the best help on a forum
http://www.sqlservercentral.com/articles/Best+Practices/61537
-
Just another option.
WITH
E(n) AS(
SELECT n FROM (VALUES(0),(0),(0),(0),(0),(0),(0),(0),(0),(0))E(n)
),
E2(n) AS(
SELECT a.n FROM E a, E b
),
E4(n) AS(
SELECT a.n FROM E2 a, E2 b
),
cteTally(n) AS(
SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) n
FROM E4
)
SELECT n
FROM cteTally
WHERE n NOT LIKE '%0%0%'
AND n NOT LIKE '%1%1%'
AND n NOT LIKE '%2%2%'
AND n NOT LIKE '%3%3%'
AND n NOT LIKE '%4%4%'
AND n NOT LIKE '%5%5%'
AND n NOT LIKE '%6%6%'
AND n NOT LIKE '%7%7%'
AND n NOT LIKE '%8%8%'
AND n NOT LIKE '%9%9%'; -
This is actually a fairly easy number to calculate. It's a variation on n choose k. The first digit can be any digit except zero. The remaining digits (k) can be any of the 9 remaining digits (n). So the number of 5 digit numbers would be 9 * ( 9 choose 4) or 1134.
Drew
Edit: Forgot to multiply by 9.
J. Drew Allen
Business Intelligence Analyst
Philadelphia, PA -
Thanks for the quick replies.
But there is no limitation for the length.
So:
3 is correct and belongs to the set.
7543 is correct and belongs in the set
8765432 is correct and belongs in the set.876543261 is NOT in the set, digit 6 is repeated, so this is not a correct number.
The integer 0007543 is the same as integer 7543 so this does not count as an extra integer number.
Ben - ben.brugman - Thursday, March 2, 2017 9:04 AM
So 0 is the lower bound and 9,876,543,210 is the upper bound?
The absence of evidence is not evidence of absence.
Martin ReesYou can lead a horse to water, but a pencil must be lead.
Stan Laurel - drew.allen - Thursday, March 2, 2017 8:33 AM
For 5 positions I got a different number of possibilities.
Starting with 10234, 10235 and finishing with 98763, 98764, 98765.
My number of possibilities is far greater than 1134 for a 5 positions number.
(Correct is that a 5 position number can start with 9 different digits.)I did the calculations of combinations and/or permutations in Excel, but would like to have a complete solution in SQL. (Not using the same calculation as done in Excel).
Thanks for your anwser,
Ben - ben.brugman - Thursday, March 2, 2017 9:04 AM
there must be a limit...if you have no recurring single integers then 9,876,543,210 is the max number....surely??
________________________________________________________________
you can lead a user to data....but you cannot make them think
and remember....every day is a school day - ben.brugman - Thursday, March 2, 2017 9:04 AM
The limitation for the length on my example is really easy to do. You just put a TOP(N) on the cteTally where N is 10^DesiredLength. You might want to add more cross joins to get enough digits. For 7 digits, it completed in 8 seconds.
- Phil Parkin - Thursday, March 2, 2017 9:11 AM
Yes.
- Luis Cazares - Thursday, March 2, 2017 9:16 AM
There is NO limitation on lenght. Any lenght is allowed, but as allready answered (with some logic) there can be no integer higher than : 9876543210, because any integer with 11 positions must have two positions which contain the same digit.
Your method of testing is faster than what I came up with.
Your method does solve the problem for different lengths.
But for a length of 10 it is a tad 'slow'.
You have ommitted the 0 as an integer.So your testing incorperated in 'my' code (actually same principle).
(I replaced my testing. Still a tad slow for 10 positions.
But about 10 times faster than my own testing. 102 seconds if limited to 8 positions).
;
WITH
L0 AS(SELECT 0 AS c UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0), -- 4
L1 AS(select 0 as x from L0 A, L0 B, L0 C, L0 D), -- 4 ^4 = 256
L2 AS(select 0 as x from L1 A, L1 B, L1 C, L1 D), -- (4 ^ 4) ^4 = 4 Giga
L3 AS(select 0 as x from L0 A, L2 B -- 4* (4 ^ 4) ^4 = 16 Giga = 17179869184
L9 AS(Select row_number() OVER(PARTITION BY 1 order by x )-1 as n from L3) -- voeg rijnummers toe
SELECT COUNT(*)
FROM L9
WHERE n NOT LIKE '%0%0%'
AND n NOT LIKE '%1%1%'
AND n NOT LIKE '%2%2%'
AND n NOT LIKE '%3%3%'
AND n NOT LIKE '%4%4%'
AND n NOT LIKE '%5%5%'
AND n NOT LIKE '%6%6%'
AND n NOT LIKE '%7%7%'
AND n NOT LIKE '%8%8%'
AND n NOT LIKE '%9%9%'I am going to try your 'end testing' with generating 'substrings' which do not contain any double digits.
First generate a string of 2 digits not containing doubles, then generate a string of 4 digits not containing doubles. Then combining 4 and 4 not containing doubles, then combining 8 and 2 not containing doubles.
So that at any time the number of rows is far less than 10^10.
Problem here again is accounting for different length strings. Thinking of generating strings starting with a number of 'x'ses, so that the shorter strings are accounted for.
Still working on this.Thanks,
Ben - J Livingston SQL - Thursday, March 2, 2017 9:14 AM
There is no limit in length in the question.
But yes logic dictates that 9876543210 is the max number SURELY.But there is no limitation of length stated in the question.
Thanks for your replay,
Ben
Viewing 15 posts - 1 through 15 (of 37 total)
You must be logged in to reply to this topic. Login to reply