[Solved] all possible combinations

Discuss the spreadsheet application

[Solved] all possible combinations

Postby dodgeitorelse » Sat Sep 02, 2017 3:28 pm

I have searched for answers on this forum and the closest I found was Combinations and Permutations, however all answers seem to show that each item is used only once. I have numbers 1-8 and I want to use 5 out of the 8 in my results. I also want to have results shown with a hyphen seperator. I want to find all possible combinations where each number can be used more than once for example one result could be 7-7-7-7-7. I want to display all combinations in a single column. What have I overlooked to be able to do this? Any help will be greatly appreciated. I am not asking for the code to be written for me. I would prefer to be pointed in the right direction so I can learn for myself how to do this. Again thank you.
Last edited by RoryOF on Sat Sep 02, 2017 6:50 pm, edited 2 times in total.
Reason: Added green tick [RoryOF, Moderator]
OpenOffice 4.1.3
Windows 10 Home
dodgeitorelse
 
Posts: 3
Joined: Sat Sep 02, 2017 3:07 pm

Re: all possible combinations

Postby Zizi64 » Sat Sep 02, 2017 4:04 pm

Tibor Kovacs, Hungary; LO6.1.6 on Win7-10 x64Prof.
PortableApps/winPenPack: LO3.3.0-6.3.3; AOO4.1.6
Please, edit the initial post in the topic: add the word [Solved] at the beginning of the subject line - if your problem has been solved.
User avatar
Zizi64
Volunteer
 
Posts: 8542
Joined: Wed May 26, 2010 7:55 am
Location: Budapest, Hungary

Re: all possible combinations

Postby Villeroy » Sat Sep 02, 2017 4:59 pm

Trivial to do with a database.
Attachments
topc90200.ods
5 out of 8
(110.65 KiB) Downloaded 123 times
Please, edit this topic's initial post and add "[Solved]" to the subject line if your problem has been solved.
Ubuntu 18.04, no OpenOffice, LibreOffice 6.x
User avatar
Villeroy
Volunteer
 
Posts: 27381
Joined: Mon Oct 08, 2007 1:35 am
Location: Germany

Re: all possible combinations

Postby jrkrideau » Sat Sep 02, 2017 5:05 pm

I don't think that Calc (or any other spreadsheet) is a good tool for this. Assuming I have a) understood what you want and b) have not mucked up the calculations you will end up with 32768 permutations.

You might be better off with a procedural language such as Python or, perhaps Perl.

For that matter, I believe that both Python and Perl come with permutation and combination functions.
OpenOffice 4.1.6; Ubuntu 18.04
jrkrideau
Volunteer
 
Posts: 3716
Joined: Sun Dec 30, 2007 10:00 pm
Location: Kingston Ontario Canada

Re: all possible combinations

Postby dodgeitorelse » Sat Sep 02, 2017 5:33 pm

Thank you all for your replies. Yes, it is permutations and yes result is 32,768. I had so much data in my spread sheet prior to trying to sort this problem out that I didn't want to use a database mostly because I have no idea how to work with open office databases. I do have an apache web server that I run and can run queries and such easily on that how ever I don't leave the server running all the time and I wanted to be able to use google sheets to have access from smartphone at will. I will have to rethink my situation here. Will mark this post as solved if I decide to go with server option. Please give me a few days to decide. Again, thank you all very much.
OpenOffice 4.1.3
Windows 10 Home
dodgeitorelse
 
Posts: 3
Joined: Sat Sep 02, 2017 3:07 pm

Re: all possible combinations

Postby Villeroy » Sat Sep 02, 2017 6:01 pm

File>New>Database...
[X] Create new database...
Register database: No
Save the database document.

Click the tables section.
menu:Tools>SQL... (easier than explaining the GUI)
Code: Select all   Expand viewCollapse view
CREATE TABLE T(N TINYINT PRIMARY KEY);

menu:Tools>Refresh Tables

Open the new table and enter numbers 1 to 8.

Click the queries section.
Create a query in SQL view (easier than explaining the GUI)
Code: Select all   Expand viewCollapse view
SELECT "N" AS "Number" FROM "T"

hit F5 to test the query. It selects the N column from table T under as alias "Number" (column label).

Next step:
Code: Select all   Expand viewCollapse view
SELECT "T1"."N" AS "N1", "T2"."N" AS "N2"
FROM "T" AS "T1", "T" AS "T2"

This one takes 2 times the same table T as alias T1 and T2 and selects the N column from both of them as alias N1 and N2. What you see is all combinations of rows from both tables (8x8 rows).

More of the exact same stuff:
Code: Select all   Expand viewCollapse view
SELECT "T1"."N" AS "N1", "T2"."N" AS "N2", "T3"."N" AS "N3", "T4"."N" AS "N4", "T5"."N" AS "N5"
FROM "T" AS "T1", "T" AS "T2", "T" AS "T3", "T" AS "T4", "T" AS "T5"

Click the >| button near the bottom of the window and wait a few seconds. It calculates the full list and takes you to the last record #32768.

Instead of selecting the individual numbers, you can concatenate them like you would do in a spreadsheet.
'-' in single quotes is a literal hyphen ("-" in a spreadsheet).
|| (two pipes) are the concatanation operator (& in a spreadsheet)
Code: Select all   Expand viewCollapse view
SELECT "T1"."N" || '-' || "T2"."N" || '-' || "T3"."N" || '-' || "T4"."N" || '-' || "T5"."N" AS "Concatenation"
FROM "T" AS "T1", "T" AS "T2", "T" AS "T3", "T" AS "T4", "T" AS "T5"


Save the query, close it, copy the query icon and paste into a spreadsheet.
Please, edit this topic's initial post and add "[Solved]" to the subject line if your problem has been solved.
Ubuntu 18.04, no OpenOffice, LibreOffice 6.x
User avatar
Villeroy
Volunteer
 
Posts: 27381
Joined: Mon Oct 08, 2007 1:35 am
Location: Germany

Re: all possible combinations

Postby dodgeitorelse » Sat Sep 02, 2017 6:35 pm

WOW!! That was easy enough, thank you!
OpenOffice 4.1.3
Windows 10 Home
dodgeitorelse
 
Posts: 3
Joined: Sat Sep 02, 2017 3:07 pm

Re: [Solved] all possible combinations

Postby MrProgrammer » Sat Sep 02, 2017 7:46 pm

dodgeitorelse wrote:I have numbers 1-8 and I want to use 5 out of the 8 in my results. I also want to have results shown with a hyphen seperator. I want to find all possible combinations where each number can be used more than once for example one result could be 7-7-7-7-7.
This is simple with a spreadsheet too. They are the the five-digit base-eight numbers (8⁵ = 32768 of them) except:
• You want to use 8 instead of 0
• You want to insert some hyphens

In A2 put =REPLACE(REPLACE(REPLACE(REPLACE(SUBSTITUTE(BASE(ROW()-2;8;5);"0";"8");5;0;"-");4;0;"-");3;0;"-");2;0;"-") then fill the formula down to A32769. If you prefer to see the values in lexicographic order:
Edit → Select All
Edit → Copy
Edit → Paste Special → Paste All → Text → Formulas → OK
Data → Sort.

[Tutorial] Ten concepts that every Calc user should know
Mr. Programmer
AOO 4.1.7 Build 9800 on MacOS 10.14.6.   The locale for any menus or Calc formulas in my posts is English (USA).
User avatar
MrProgrammer
Moderator
 
Posts: 3896
Joined: Fri Jun 04, 2010 7:57 pm
Location: Wisconsin, USA

Re: [Solved] all possible combinations

Postby acknak » Sat Sep 02, 2017 9:24 pm

And, just for fun, here's a Perl (6) one liner:

$ perl6 -e 'my @d=(1..8); say .join("-") for (@d X @d X @d X @d X @d)'
1-1-1-1-1
1-1-1-1-2
1-1-1-1-3
...
8-8-8-8-6
8-8-8-8-7
8-8-8-8-8

(X is the cross product operator)

To manage the general case with only a spreadsheet, some manual manipulations are required (as far as I can see).

Mr Programmer's suggestion seems the simplest and most efficient.

Another (more brute-force) approach is to build up the result as a series of (take each previous element and append each of the set of elements). For the first step, the previous step is empty, so appending each of the elements produces 1..8. For the next step, take 1, append each of the elements, producing 1-1..1-8, 2-1..2-8, ... 8-8; third round: 1-1-1..1-1-8, 1-2-1..1-2-8, ... 8-8-8 and so on.

I used a separate sheet for each step: sheet1 is just the elements 1..8, sheet2 joins two elements, sheet3 joins the results from sheet2 with the elements, sheet4: sheet3 X elements, sheet5: sheet4 X elements. Each sheet uses the same formulas, accessing the previous sheet. To build up the steps, you just have to make a new sheet, find how many cells to fill (sheet2:8x8=64, sheet3:64x8=512, sheet4:512x8=4096, sheet5:4096x8=32768, ...) and then copy/paste/fill the formulas into those rows.

This approach is limited to six-element combinations: 8^6=262144 rows; 8^7=2097152, twice as many rows as Calc can handle.

Each step requires just a bit of arithmetic to select which elements to join. The next result from the previous step (sheet) is returned by =OFFSET(prev;QUOTIENT(ROW()-1;xb);0) And the element to append is returned by =OFFSET(elems;MOD(ROW()-1;xb);0). Where prev is A1 on the previous sheet; elems is A1 on the first sheet; and xb is just the "base" or count of elements: 8

The full sheet is too big to attach, but here's a version cut down to three steps/sheets. To fill it out, copy Sheet3.A1:C1 to Sheet4.A1:C4096 and Sheet5.A1:C32768.
Attachments
crossproduct_8_3.ods
(18.51 KiB) Downloaded 57 times
AOO4/LO5 • Linux • Fedora 23
User avatar
acknak
Moderator
 
Posts: 22756
Joined: Mon Oct 08, 2007 1:25 am
Location: USA:NJ:E3

Re: [Solved] all possible combinations

Postby Zizi64 » Sat Sep 02, 2017 9:58 pm

Here is an another approach:

Formatted combination.ods
(13.28 KiB) Downloaded 156 times
Tibor Kovacs, Hungary; LO6.1.6 on Win7-10 x64Prof.
PortableApps/winPenPack: LO3.3.0-6.3.3; AOO4.1.6
Please, edit the initial post in the topic: add the word [Solved] at the beginning of the subject line - if your problem has been solved.
User avatar
Zizi64
Volunteer
 
Posts: 8542
Joined: Wed May 26, 2010 7:55 am
Location: Budapest, Hungary

Re: [Solved] all possible combinations

Postby BeeRayDee » Tue Nov 19, 2019 7:16 am

Curious if you have found the solution you were seeking.
I completely understand the question, looking for the solution as well.
These responses are literal, and do not help if you are looking to sort the results, they have only given you the formulas, or just the results of the combinations.
I have been using Python for 'combinations' but Calc is more managable when it comes to handling useful results.
Google sheets on your phone? Good idea!
Perhaps I'll see you trackside one day...
Linux - Ubuntu 20x
LibreOffice 6.3.3
BeeRayDee
 
Posts: 1
Joined: Tue Nov 19, 2019 6:43 am

Re: [Solved] all possible combinations

Postby keme » Tue Nov 19, 2019 12:20 pm

BeeRayDee wrote:Curious if you have found the solution you were seeking.
I completely understand the question, looking for the solution as well.
...

SQL cross joins and the "set cross product" (or "cartesian product") readily available in some programming languages (like the PERL example by acknak above) easily make the requested set of permutations.

For Calc, I think the approach given by Zizi64 is by far the simplest. It may be extended to account for different size permutation and number of variations, by using the BASE() function instead of octal targeted functions. If you limit variation to digits (i.e. max ten different objects, from zero to nine), you can still work with plain number formatting and avoid the clutter of string manipulation.

Also, if you want a complete list in a manageable format ("single file" table) you are limited to the one million (2^20=1048576, to be exact) rows available for a spreadsheet. If you need to pick a few permutations at random, without requiring the entire set of permutations available at all times, you can work with larger sets.

See attachment.
Attachments
permutations.ods
(18.74 KiB) Downloaded 4 times
User avatar
keme
Volunteer
 
Posts: 3286
Joined: Wed Nov 28, 2007 10:27 am
Location: Egersund, Norway


Return to Calc

Who is online

Users browsing this forum: No registered users and 36 guests