Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This would be pretty easy without duplication . . . for</p> <pre><code>{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 } </code></pre> <p>Since you only have 9 distinct choices (as opposed to the 10 in the original problem), the answer should be 9! / (9 - 4)!</p> <p>( By the way, you can actually have more different 4-digit numbers if you allow repetition, i.e. 4456. Then the answer would just be 9^4 4-digit numbers. )</p> <p>Similarly, {1, 1, 2, 2, 3, 4, 5, 6, 7, 8 } has 8 distinct choices, so the answer should be 8! / (8 - 4)! by your original math.</p> <p><strong>Edit and actual answer</strong>: Maybe you meant that if the 1 is duplicated in your set, you can use two 1's in the answer?</p> <p>Edit 2: Working, tested python module provided</p> <p>In that case, you might try calculating the distinct number of possibilities, and then adding the results with duplicates, as the following python code suggests):</p> <pre><code>import math def set_exclude(a, b): result = [] for i in a: if not i in b: result.append(i) return result def cnt_unique(aset, choices_picked, count_left, count_total): # Sanity check if count_left &lt; 0: return 0 if count_left == 0: return math.factorial(count_total) # Do non-duplicate combinations first # Set unprocessed = (set without any elements in choices_picked) unprocessed = set_exclude(aset, choices_picked) temp = len(set(unprocessed)) # If we have no more valid items to choose from, this is impossible if temp &gt;= count_left: result = math.factorial(temp) / math.factorial(temp - count_left) / \ math.factorial(count_left) * math.factorial(count_total) else: result = 0 # Now find duplicate-involving combinations for member in set(unprocessed): valid = True for contest in choices_picked: if contest &gt;= member: valid = False break if valid: count = unprocessed.count(member) new_choices = choices_picked + [ member ] for i in range(2, count+1): result_temp = cnt_unique(aset, new_choices, \ count_left - i, count_total) if result_temp != 0: result_temp //= math.factorial(i) result += result_temp return result aset = [ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 ] result_size = 4 combinations = cnt_unique(aset, [], result_size, result_size) </code></pre> <p>OK, I've verified by hand that algorithm works for all of your cases presented above. I'm fairly confident it works in more general cases, but I don't have time at the moment to do any additional test cases (for instance, if there were 3 1's, or 3 groups of duplicates). Note it would also blow up if there were no numbers in set which were not in choices_picked (ie you have one unique number duplicated 10 times).</p> <p>Edit 3: Regarding how many function calls are made with this algorithm for large sets, I tested with the following function call, incrementing a variable once for each non-trivial (count_left >= 0) call to cnt_unique:</p> <pre><code>&gt;&gt;&gt; def test(): b = [0] c = time.time() result = cnt_unique(range(1,51) + range(1,51), [], 4, 4, b) c = time.time() - c print("Result: " + str(result)) print("Time: " + str(c)) print("Calls: " + str(b[0])) &gt;&gt;&gt; test() Result: 6240150 Time: 0.0150001049042 Calls: 1276 </code></pre> <p>So, for a 100 element set with 2 entries for each number 1-50, there were 1276 calls. And it executes quite fast; one tick with time.time() is 15 ms, so it executes in typically less than 15 ms.</p>
    singulars
    1. This table or related slice is empty.
    1. POCombinatorics with repeated chars on initial group
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USWalt W
    1. USWalt W
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI think you should be able to have two 1s.
      singulars
      1. PO
      1. USSean
    2. COHe wants to include repetition, so the vector, 1122 is valid, but it wont represent 4 different values in the n!/(n-d)! equation. at least based on his numbers, since 9!/(9-4)! != 3360
      singulars
      1. PO
      1. USnlucaroni
    3. COexactly. On the group { 1,1,2,3,4,5,6,7,8,9 } 1123 should be a valid combination
      singulars
      1. PO
      1. USguigouz
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload