#s of Combinations and Permutations of lines?

[Laubarr]

Hello All,

See picture below:

There exist an infinite plane with infinite number of dots. For sake of argument, let's assume they are 1 inch away from each other.

However, below(on your far left) you can see 3 lines already made. The last line is the yellow one.
What you see on the right, are all combinations of possible moves. Move is defined as structure of lines until you reach an empty dot.
Thus, there are 6 combinations of single line(on top). While on bottom you see 10 combinations. 5 of them moves with 2 lines, and 5 with 3 lines.
Total # of combinations is 16.

 

So far so good?
Well the basic unsolved question are:
* Does formula exist to calculate total number of combinations(16 in this case) just by looking at the initial graph of 3 lines?
** Does formula exist to show the breakdown of all combinations (6 for single line, 5 for 2 lines, 5 for 3 lines?
*** is 16 the biggest number of combinations that you can make from 3 line starting configuration? For instance: Try to calculate # of combinations (1 lines, 2 lines, 3 lines) from this initial variation:

To not spoil the fun, i will just say there is more than 16. So is this the best solution? How we can prove that this is the best we can do? Obviously we can prove that just by doing all 3 line configurations by hand, but what if we take it to next level? What's the best 4 line configuration and how many combinations it has? How about 5,6.7...(n) ? The tree expands quite rapidly, and also few things need to be explained:

Combinations vs Permutations:
 

Above, there are 4 lines as starting configuration. In this case, there are 36 combinations OR 41 permutations. The reason is because you can go from A > B > C > D or C > B > A > D. Once again, is there a formula to calculate combinations (36) and Permutation(41) from any starting configuration?
 

Notation + Final info to consider:
 

Using above notation, you can notice that each configuration is unique and might have different #s of combinations and or permutations. For example:
 

Anyone with any input, either mechanical or potentially writing a code to get the answers How many combinations/Permutations for each variation with up to 10 lines as a starting configuration, would be greatly appreciated. If your program can handle bigger starting configurations, that's even better!

Thank You and enjoy! 

[EventHorizon]

So people don't need to register for an account at mathhelpboards.com to see those images...

On 9/27/2020 at 10:53 AM, Laubarr said:

Hello All,

See picture below:

There exist an infinite plane with infinite number of dots. For sake of argument, let's assume they are 1 inch away from each other.

However, below(on your far left) you can see 3 lines already made. The last line is the yellow one.
What you see on the right, are all combinations of possible moves. Move is defined as structure of lines until you reach an empty dot.
Thus, there are 6 combinations of single line(on top). While on bottom you see 10 combinations. 5 of them moves with 2 lines, and 5 with 3 lines.
Total # of combinations is 16.

So far so good?
Well the basic unsolved question are:
* Does formula exist to calculate total number of combinations(16 in this case) just by looking at the initial graph of 3 lines?
** Does formula exist to show the breakdown of all combinations (6 for single line, 5 for 2 lines, 5 for 3 lines?
*** is 16 the biggest number of combinations that you can make from 3 line starting configuration? For instance: Try to calculate # of combinations (1 lines, 2 lines, 3 lines) from this initial variation:

To not spoil the fun, i will just say there is more than 16. So is this the best solution? How we can prove that this is the best we can do? Obviously we can prove that just by doing all 3 line configurations by hand, but what if we take it to next level? What's the best 4 line configuration and how many combinations it has? How about 5,6.7...(n) ? The tree expands quite rapidly, and also few things need to be explained:

Combinations vs Permutations:

Above, there are 4 lines as starting configuration. In this case, there are 36 combinations OR 41 permutations. The reason is because you can go from A > B > C > D or C > B > A > D. Once again, is there a formula to calculate combinations (36) and Permutation(41) from any starting configuration?

Notation + Final info to consider:

Using above notation, you can notice that each configuration is unique and might have different #s of combinations and or permutations. For example:

Anyone with any input, either mechanical or potentially writing a code to get the answers How many combinations/Permutations for each variation with up to 10 lines as a starting configuration, would be greatly appreciated. If your program can handle bigger starting configurations, that's even better!

Thank You and enjoy! 

 

[EventHorizon]

Some maximum permutations/combinations

Spoiler

Starting Configuration Length, Max Permutations, Max Combinations

0,8,8
1,7,7
2,12,12
3,20,20
4,45,36
5,104,64
6,245,112
7,795,240
8,2907,511
9,10401,1088
10,33997,?

Some code (yay for global variables.... yeah... i was lazy)

Spoiler

#include <stdio.h>
#include <string.h>
#include <cstdlib>

#define MAX_MOVES 100
unsigned char used_dir[MAX_MOVES*2+1][MAX_MOVES*2+1];
unsigned char path[4*MAX_MOVES];
unsigned char path_max_p[4*MAX_MOVES];
unsigned char path_max_c[4*MAX_MOVES];
int mode;
int length;
int conflength;
int max_p_found;
int max_c_found;
int start_length;
int moves;
int more_moves;
int clength;
int moves_target;
int x;
int y;
int permtotal;
int combocount;
float combototal;
int dirs[9][2] = {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}, {0,0}};

void set_used(int dir){used_dir[x][y] |= 1<<dir;}
void clear_used(int dir){used_dir[x][y] &= ~(1<<dir);}
char is_used(int dir){return used_dir[x][y] & (1<<dir);}
int is_used_node(int dir){return used_dir[x+dirs[dir][0]][y+dirs[dir][1]] == 0 ? 0 : 1;}
void print_path(){for(int i=0; i<length; i++) printf("(%i)",path[i]); printf("\n");}

void move(int dir)
{
    if (!is_used_node(dir)) moves++;
    path[length++] = dir;
    set_used(dir);
    x += dirs[dir][0];
    y += dirs[dir][1];
    set_used((dir+4)%8);
}

void unmove(int dir)
{
    clear_used((dir+4)%8);
    x -= dirs[dir][0];
    y -= dirs[dir][1];
    clear_used(dir);
    length--;
    if (!is_used_node(dir)) moves--;
}

void cmove(int dir)
{
    clength++;
    clear_used(dir);
    x += dirs[dir][0];
    y += dirs[dir][1];
    clear_used((dir+4)%8);
}

void cunmove(int dir)
{
    clength--;
    set_used((dir+4)%8);
    x -= dirs[dir][0];
    y -= dirs[dir][1];
    set_used(dir);
}

void combo_rec()
{
    if (clength == length) {combocount++; return;}
    for (int i = 0; i < 8; i++)
        if (is_used(i)) {cmove(i); combo_rec(); cunmove(i);}
}

void do_combo_check()
{
    combocount = 0;
    clength=0;
    int savex = x;
    int savey = y;
    x = y = MAX_MOVES;
    for(int i = 0; i < start_length; i++) cmove(path[i]);
    combo_rec();
    for(int i = start_length-1; i >= 0; i--) cunmove(path[i]);
    combototal += 1.0f / (float)combocount;
    x = savex;
    y = savey;
}

void permute_rec()
{
    if (moves == moves_target)
    {
        if (mode != 4) do_combo_check();
        if (mode==1) printf("%i,%i    ",length,combocount);
        if (mode==1) print_path();
        permtotal++;
        return;
    }
    for(int i = 0; i < 8; i++)
        if (!is_used(i)) {move(i); permute_rec(); unmove(i);}
}

void config_rec()
{
    if (length == conflength)
    {
        permtotal = 0;
        combototal = 0;
        start_length = length;
        moves_target = moves + more_moves;

        permute_rec();

        if (mode == 2)
        {
            print_path();
            printf("Permutations = %i\n", permtotal);
            printf("Combinations = %i\n", (int)(combototal+0.0001f));
        }

        if (permtotal > max_p_found) {max_p_found = permtotal; memcpy(&path_max_p,&path,conflength);}
        if (combototal > max_c_found) {max_c_found = combototal; memcpy(&path_max_c,&path,conflength);}
        return;
    }

    int min = 0;
    int max = 8;
    if (length == 0) {max = 2;}
    if (length == 1) {min = path[0]; max = path[0]+4;}
    for(int i = min; i < max; i++)
        if (!is_used(i)) {move(i); config_rec(); unmove(i);}
}

 

int main(int argc, char *argv[])
{
    if (argc != 4) {printf("Usage 1: lines 1 <config> <more>\nUsage 2: lines 2 <length> <more>\n<config> is an initial configuration like 7436\n<length> is the length of initial configurations to search over\n<more> is the additional moves taken.\n"); return 0;}
    mode = argv[1][0]-'0';

    x = y = MAX_MOVES;
    length = moves = 0;
    permtotal = 0;
    combototal = 0;
    memset(&used_dir,0,sizeof(used_dir));

    
    more_moves = std::strtol(argv[3],0,10);
    if ((more_moves < 1) || (more_moves > 10)) printf("More moves out of bounds.");

    if (mode == 1)
    {
        while (1)
        {
            int nextdir = argv[2][length] - '0';
            if ((nextdir < 0) || (nextdir > 7)) break;
            move(nextdir);
        }
        
        start_length = length;
        moves_target = moves + more_moves;

        permute_rec();
        printf("Permutations = %i\n", permtotal);
        printf("Combinations = %i\n", (int)(combototal+0.0001f));
        return 0;
    }

 

    if ((mode == 2) || (mode == 3) || (mode == 4))
    {
        conflength = std::strtol(argv[2],0,10);
        if ((conflength > 50) || (conflength < 0)) {printf("Length out of bounds.\n"); return 0;}
        
        max_p_found = max_c_found = 0;

        config_rec();

        printf("Most permutations = %i : First found = ", max_p_found);
        for(int i=0; i<conflength; i++) printf("(%i)",path_max_p[i]); printf("\n");
        printf("Most combinations = %i : First found = ", max_c_found);
        for(int i=0; i<conflength; i++) printf("(%i)",path_max_c[i]); printf("\n");
        return 0;
    }

    printf("Usage 1: lines 1 <config> <more>\nUsage 2: lines 2 <length> <more>\n<config> is an initial configuration like 7436\n<length> is the length of initial configurations to search over\n<more> is the additional moves taken.\n");
}

 

code also attached.

main.cpp

Example usage

Spoiler

I named the executable "lines"

The first argument is the mode.  Mode 1 will expect argument 2 to be a string of numbers 0-7 representing the initial configuration, and argument 3 will be the number of moves to add on to it.

Mode 2 will search over all initial configurations of length <argument 2>, adding <argument 3> number of moves to it.  I added a mode 3 (quiet) and mode 4 (quiet and don't find combinations).

So if I run "./lines 1 7436 1", it would show all the possibilities starting with the initial configuration of 7436 (the first two numbers on the line are the length of the path and how many different permutations use the same lines (used to calculate combinations)), then list the totals of 41 permutations and 36 combinations.

If I run "./lines 2 5 1", it would list the number of permutations and combinations for all initial configurations of length 5 (though not the ones that start with directions 2-7, and only half the possibilities for the second line direction.  This is to cut down on reflections/rotations that would be equivalent.).  It would end by printing:

"Most permutations = 104 : First found = (0)(3)(4)(4)(7)
Most combinations = 64 : First found = (1)(4)(5)(4)(1)"