March 2, 2017 at 9:58 am
9!+8!+7!+6!+5!+4!+3!+2!+1
https://www.mathsisfun.com/combinatorics/combinations-permutations.html
For fast, accurate and documented assistance in answering your questions, please read this article.
Understanding and using APPLY, (I) and (II) Paul White
Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff Moden
March 2, 2017 at 10:05 am
Try this:
WITH Factorials (Number, Factorial) AS (
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 UNION ALL
SELECT 10, 3628800
)
, Recursion AS (
SELECT
1 AS NoofDigits
, 10 AS Number
, CAST('10 * 9' AS varchar(max)) AS ShowWorking0
, CAST('10' AS varchar(max)) AS ShowWorking
UNION ALL
SELECT
NoofDigits + 1
, 3628800/f.Factorial - r.Number
, ShowWorking0 + ' * ' + CAST(9-NoofDigits AS varchar(max))
, ShowWorking0 + ' * ' + ' - ( ' + ShowWorking + ' )'
FROM Recursion r
JOIN Factorials f ON 9 - r.NoofDigits = f.Number
WHERE NoofDigits <= 10
)
SELECT
NoofDigits
, Number
, ShowWorking
FROM Recursion
UNION ALL
SELECT
0
, SUM(Number)
, 'Grand Total'
FROM Recursion;
March 2, 2017 at 10:14 am
ChrisM@Work - Thursday, March 2, 2017 9:58 AM9!+8!+7!+6!+5!+4!+3!+2!+1
https://www.mathsisfun.com/combinatorics/combinations-permutations.html
This does not come up with the correct anwser.
positions Number of integers
1 10 0,1,2,3,4,5,6,7,8,9
2 81 10,12,13,14,15,16,17,18,19,20,21,23,24 ...... 97,98
3 648 102,103 ....... 986,987
: :
The total of this (max 9 positions ?) does nog agree with 9!+8!+7!+6!+5!+4!+3!+2!+1! = 409113
The total of this (max 10 positions) does nog agree with 10!+9!+8!+7!+6!+5!+4!+3!+2!+1! = 4037913 does neither
Thanks for the reference.
Ben
March 2, 2017 at 10:18 am
ben.brugman - Thursday, March 2, 2017 10:14 AMChrisM@Work - Thursday, March 2, 2017 9:58 AM9!+8!+7!+6!+5!+4!+3!+2!+1
https://www.mathsisfun.com/combinatorics/combinations-permutations.html
This does not come up with the correct anwser.
positions Number of integers
1 10 0,1,2,3,4,5,6,7,8,9
2 81 10,12,13,14,15,16,17,18,19,20,21,23,24 ...... 97,98
3 648 102,103 ....... 986,987
: :The total of this (max 9 positions ?) does nog agree with 9!+8!+7!+6!+5!+4!+3!+2!+1! = 409114
The total of this (max 10 positions) does nog agree with 10!+9!+8!+7!+6!+5!+4!+3!+2!+1! = 4037914 does neitherThanks for the reference.
Ben
Oops - should be 10!+9!...
When you say the results are incorrect, how have you calculated your result - and what is it?
For fast, accurate and documented assistance in answering your questions, please read this article.
Understanding and using APPLY, (I) and (II) Paul White
Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff Moden
March 2, 2017 at 10:36 am
John Mitchell-245523 - Thursday, March 2, 2017 10:05 AMTry this:
WITH Factorials (Number, Factorial) AS (
SELECT 1, 1 UNION ALL
SELECT 2, 2 UNION ALL
SELECT 3, 6 UNION ALL
Thanks for this extensive answer,
But looking at the second line, the number of 2 digit integers is 81.
Looking at the third line, the number of 3 digit numbers is 648
The anwser are close in the beginning, but start to deviate for the longer numbers.
So thanks for the extensive answer.
The anwser given by Luis Cazares, produces the 'correct' results, although the 0 has to be added, extend the query to accomodate the longest (9876543210) number. Warning, extending the query makes it slow.
See below the signature for the code to test this.
Ben
Code by Luis Cazares, which shows the results for the length 1, 2, 3, 4
Change the length in the last line, works for lengths of 1,2,3,4.
Code can be extended beyond that, but needs more rows and becomes far slower. (use the other L1, L2 and L3 for this).
;
WITH
-- L0 AS(SELECT 0 AS c UNION ALL SELECT 0 UNION ALL SELECT 0 UNION ALL SELECT 0), -- 4
L0 AS(SELECT N FROM (VALUES(0),(0),(0),(0))XXX(N)), -- 4
-- L1 AS(select 0 as x from L0 A, L0 B, L0 C, L0 D), -- 4 ^4 = 256
L1 AS(select 0 as x from L0 A, L0 B, L0 C, L0 D, L0 E, L0 F, L0 G), -- 4 ^7 = 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
L9 AS(Select row_number() OVER(PARTITION BY 1 order by x )-1 as n from L1) -- voeg rijnummers toe
SELECT *
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%'
and DATALENGTH(CONVERT(varchar(30),n)) =4
March 2, 2017 at 10:50 am
Is the total number of rows 8,877,690, by any chance?
The absence of evidence is not evidence of absence.
Martin Rees
You can lead a horse to water, but a pencil must be lead.
Stan Laurel
March 2, 2017 at 10:52 am
ChrisM@Work - Thursday, March 2, 2017 10:18 AMOops - should be 10!+9!...
When you say the results are incorrect, how have you calculated your result - and what is it?
Also the 10!+9!... Does not give the anwser.
and what is it?
That would be telling.
The anwser given by the Code by Luis Cazares, gives 'the correct number.
See the previous post for the numbers given for the 'shorter' strings. (Up to 4 long).
Ben
March 2, 2017 at 11:28 am
Phil Parkin - Thursday, March 2, 2017 10:50 AMIs the total number of rows 8,877,690, by any chance?
It's close.
Ben
March 2, 2017 at 11:36 am
One final attempt and I'll stop: how about 8,877,691?
The absence of evidence is not evidence of absence.
Martin Rees
You can lead a horse to water, but a pencil must be lead.
Stan Laurel
March 2, 2017 at 11:39 am
It's becoming a contest between:
Brain (and calculating)
and
Brute Force.
Phil Parkin can you tel how you came to this anwser ?
Was is Brainpower or Brute Force.
Offcourse for the Brute Force methode using SQL doesn't happen on itself, but depends on brainpower als wel. And for calculating some (but far less) help is used as wel.
All thanks allready for your contributions, I have picked up some pointers allready, to be used in future 'real' scripts. So thanks. (It's 19:40 here, my team is expecting me.) I'll pick this up this evening late or tomorrow. Thanks all.
Ben
From my spreadsheat I'll give the solutions for stringlengths up to 6. In my spreadsheat I have the solution for all ten positions as wel, but would like that to remain a challenge.
These can fairly easely be calculated with brute force. (Up to 8 is easy). 9 and 10 take some time.
| positions | number | total |
| 1 | 10 | 10 |
| 2 | 81 | 91 |
| 3 | 648 | 739 |
| 4 | 4536 | 5275 |
| 5 | 27216 | 32491 |
| 6 | 136080 | 168571 |
March 2, 2017 at 11:48 am
ben.brugman - Thursday, March 2, 2017 11:39 AMIt's becoming a contest between:Brain (and calculating)
and
Brute Force.Phil Parkin can you tel how you came to this anwser ?
Was is Brainpower or Brute Force.Offcourse for the Brute Force methode using SQL doesn't happen on itself, but depends on brainpower als wel. And for calculating some (but far less) help is used as wel.
All thanks allready for your contributions, I have picked up some pointers allready, to be used in future 'real' scripts. So thanks. (It's 19:40 here, my team is expecting me.) I'll pick this up this evening late or tomorrow. Thanks all.
BenFrom my spreadsheat I'll give the solutions for stringlengths up to 6. In my spreadsheat I have the solution for all ten positions as wel, but would like that to remain a challenge.
These can fairly easely be calculated with brute force. (Up to 8 is easy). 9 and 10 take some time.
positions number total 1 10 10 2 81 91 3 648 739 4 4536 5275 5 27216 32491 6 136080 168571
Maybe that maths degree came in useful after all. I won't post my solution yet, but will confirm that it uses straightforward non-repeating permutations, and allows for the fact that the count of answers with leading zeros needs to be subtracted (that's the more challenging bit).
The absence of evidence is not evidence of absence.
Martin Rees
You can lead a horse to water, but a pencil must be lead.
Stan Laurel
March 2, 2017 at 11:53 am
Phil Parkin - Thursday, March 2, 2017 11:36 AMOne final attempt and I'll stop: how about 8,877,691?
Yes, this is the anwser I got from my spreadsheet.
Could you enlighten us how you came by the anwser ?
My guess that brainpower has won. ???
Still working on a SQL based solutions (not calculating) which produces that number and the set of numbers.
That solution has to beat the anwser in less than 4 hours 🙂
Thanks,
Ben
March 2, 2017 at 12:06 pm
ben.brugman - Thursday, March 2, 2017 11:53 AMPhil Parkin - Thursday, March 2, 2017 11:36 AMOne final attempt and I'll stop: how about 8,877,691?Yes, this is the anwser I got from my spreadsheet.
Could you enlighten us how you came by the anwser ?My guess that brainpower has won. ???
Still working on a SQL based solutions (not calculating) which produces that number and the set of numbers.
That solution has to beat the anwser in less than 4 hours 🙂Thanks,
Ben
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.
The absence of evidence is not evidence of absence.
Martin Rees
You can lead a horse to water, but a pencil must be lead.
Stan Laurel
March 2, 2017 at 12:41 pm
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:
WITH E1 AS (
SELECT 0 AS N, '0' AS NSTR UNION ALL SELECT 1, '1' UNION ALL SELECT 2, '2' UNION ALL
SELECT 3, '3' UNION ALL SELECT 4, '4' UNION ALL SELECT 5, '5' UNION ALL
SELECT 6, '6' UNION ALL SELECT 7, '7' UNION ALL SELECT 8, '8' UNION ALL SELECT 9, '9'
),
NUMBERS AS (
SELECT 10 AS SORT_VALUE, '10 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR + D.NSTR + E.NSTR + F.NSTR + G.NSTR + H.NSTR + I.NSTR + J.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C, E1 AS D, E1 AS E, E1 AS F, E1 AS G, E1 AS H, E1 AS I, E1 AS J
WHERE A.N NOT IN (B.N, C.N, D.N, E.N, F.N, G.N, H.N, I.N, J.N)
AND B.N NOT IN (C.N, D.N, E.N, F.N, G.N, H.N, I.N, J.N)
AND C.N NOT IN (D.N, E.N, F.N, G.N, H.N, I.N, J.N)
AND D.N NOT IN (E.N, F.N, G.N, H.N, I.N, J.N)
AND E.N NOT IN (F.N, G.N, H.N, I.N, J.N)
AND F.N NOT IN (G.N, H.N, I.N, J.N)
AND G.N NOT IN (H.N, I.N, J.N)
AND H.N NOT IN (I.N, J.N)
AND I.N <> J.N
AND A.N <> 0
UNION ALL
SELECT 9 AS SORT_VALUE, ' 9 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR + D.NSTR + E.NSTR + F.NSTR + G.NSTR + H.NSTR + I.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C, E1 AS D, E1 AS E, E1 AS F, E1 AS G, E1 AS H, E1 AS I
WHERE A.N NOT IN (B.N, C.N, D.N, E.N, F.N, G.N, H.N, I.N)
AND B.N NOT IN (C.N, D.N, E.N, F.N, G.N, H.N, I.N)
AND C.N NOT IN (D.N, E.N, F.N, G.N, H.N, I.N)
AND D.N NOT IN (E.N, F.N, G.N, H.N, I.N)
AND E.N NOT IN (F.N, G.N, H.N, I.N)
AND F.N NOT IN (G.N, H.N, I.N)
AND G.N NOT IN (H.N, I.N)
AND H.N <> I.N
AND A.N <> 0
UNION ALL
SELECT 8 AS SORT_VALUE, ' 8 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR + D.NSTR + E.NSTR + F.NSTR + G.NSTR + H.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C, E1 AS D, E1 AS E, E1 AS F, E1 AS G, E1 AS H
WHERE A.N NOT IN (B.N, C.N, D.N, E.N, F.N, G.N, H.N)
AND B.N NOT IN (C.N, D.N, E.N, F.N, G.N, H.N)
AND C.N NOT IN (D.N, E.N, F.N, G.N, H.N)
AND D.N NOT IN (E.N, F.N, G.N, H.N)
AND E.N NOT IN (F.N, G.N, H.N)
AND F.N NOT IN (G.N, H.N)
AND G.N <> H.N
AND A.N <> 0
UNION ALL
SELECT 7 AS SORT_VALUE, ' 7 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR + D.NSTR + E.NSTR + F.NSTR + G.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C, E1 AS D, E1 AS E, E1 AS F, E1 AS G
WHERE A.N NOT IN (B.N, C.N, D.N, E.N, F.N, G.N)
AND B.N NOT IN (C.N, D.N, E.N, F.N, G.N)
AND C.N NOT IN (D.N, E.N, F.N, G.N)
AND D.N NOT IN (E.N, F.N, G.N)
AND E.N NOT IN (F.N, G.N)
AND F.N <> G.N
AND A.N <> 0
UNION ALL
SELECT 6 AS SORT_VALUE, ' 6 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR + D.NSTR + E.NSTR + F.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C, E1 AS D, E1 AS E, E1 AS F
WHERE A.N NOT IN (B.N, C.N, D.N, E.N, F.N)
AND B.N NOT IN (C.N, D.N, E.N, F.N)
AND C.N NOT IN (D.N, E.N, F.N)
AND D.N NOT IN (E.N, F.N)
AND E.N <> F.N
AND A.N <> 0
UNION ALL
SELECT 5 AS SORT_VALUE, ' 5 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR + D.NSTR + E.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C, E1 AS D, E1 AS E
WHERE A.N NOT IN (B.N, C.N, D.N, E.N)
AND B.N NOT IN (C.N, D.N, E.N)
AND C.N NOT IN (D.N, E.N)
AND D.N <> E.N
AND A.N <> 0
UNION ALL
SELECT 4 AS SORT_VALUE, ' 4 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR + D.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C, E1 AS D
WHERE A.N NOT IN (B.N, C.N, D.N)
AND B.N NOT IN (C.N, D.N)
AND C.N <> D.N
AND A.N <> 0
UNION ALL
SELECT 3 AS SORT_VALUE, ' 3 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR + C.NSTR AS RNSTR
FROM E1 AS A, E1 AS B, E1 AS C
WHERE A.N NOT IN (B.N, C.N)
AND B.N <> C.N
AND A.N <> 0
UNION ALL
SELECT 2 AS SORT_VALUE, ' 2 DIGITS' AS GROUP_TYPE,
A.NSTR + B.NSTR AS RNSTR
FROM E1 AS A, E1 AS B
WHERE A.N <> B.N
AND A.N <> 0
UNION ALL
SELECT 1 AS SORT_VALUE, ' 1 DIGIT' AS GROUP_TYPE,
A.NSTR AS RNSTR
FROM E1 AS A
)
SELECT ROW_NUMBER() OVER(ORDER BY ISNULL(GROUP_TYPE, 9999)) AS SORT_VALUE,
GROUP_TYPE,
COUNT(RNSTR) AS NUM_COUNT --RNSTR
FROM NUMBERS
GROUP BY GROUP_TYPE
WITH ROLLUP
ORDER BY SORT_VALUE;
Here's the results:SORT_VALUE GROUP_TYPE NUM_COUNT
-------------------- ---------- -----------
1 1 DIGIT 10
2 2 DIGITS 81
3 3 DIGITS 648
4 4 DIGITS 4536
5 5 DIGITS 27216
6 6 DIGITS 136080
7 7 DIGITS 544320
8 8 DIGITS 1632960
9 9 DIGITS 3265920
10 10 DIGITS 3265920
11 NULL 8877691
Steve (aka sgmunson) 🙂 🙂 🙂
Rent Servers for Income (picks and shovels strategy)
March 2, 2017 at 2:45 pm
ben.brugman - Thursday, March 2, 2017 9:11 AMdrew.allen - Thursday, March 2, 2017 8:33 AMThis 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.
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
Yeah, I was using the wrong formula. My formula would work if the order didn't matter, but the order does matter.
Drew
J. Drew Allen
Business Intelligence Analyst
Philadelphia, PA
Viewing 15 posts - 16 through 30 (of 37 total)
You must be logged in to reply to this topic. Login to reply