Return to Question

Recently, I came across the following problem:

Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a "chain" a maximal substring of $S$ of consecutive ones. We define $l_n(S_{s_1,s_2,...,s_k})$ as the number of chain with lenght $n$, and we denote with $L(S_{s_1,s_2,\dots,s_k})$ the element $(l_1(S_{s_1,s_2,\dots,s_k}),l_2(S_{s_1,s_2,\dots,s_k}),\dots,l_n(S_{s_1,s_2,\dots,s_k}),\dots)\in \mathbb{N}^\mathbb{N}$. We define "partial permutation" of $S_{s_1,s_2,\dots,s_k}$ a string obtained by the concatenation of $z_1, z_2, \dots, z_k$, where each $z_i$ is a string obtained by reordering the characters of $s_i$. Finally a partial permutation $Z$ of $S_{s_1,s_2,\dots,s_k}$ is called "optimal" if $L(Z)$ is a minimal element in $\mathbb{N}^\mathbb{N}$ with the colexicographic order.

Problem: Find an algorithm that produces an otimal partial permutation of $S_{s_1,s_2,\dots,s_k}$

Example: If $s_1=1, s_2=110, s_3=00010, s_4=100011, s_5=110$, a optimal partial permutation is $Z=1*011*00010*101010*101$ since $L(Z)=(7,1,0,0,\dots)$, and we cannot produce any string without a chain of lenght $2$ (becouse of $s_1$ and $s_2$)

I have some ideas to produce "good" partial permutation, but those are not always optimal. Another idea I got is to collapse string based on their number of 0s and 1s: for example every string with $n\geq2$ zeros and $n+1$ ones can always be collapsed to $101$ or $110$ or $011$ or $01110$. Then we create the optimal partial permutation reasoning on the collapsed string, but this is still far from being an algorithm.

I'm not sure if this problem is known; however, any references to articles dealing with this problem or similar ones are welcome.

EDIT: Someone asked me where this problem comes from. The question arises from practical reasons for optimizing production plans. Suppose you have a production chain structured in 30 phases. Each phase must have the same duration as all the others to ensure smooth progress in the production process. Suppose that phases 10, 11 and 12 need to produce similar objects (for example of the same color) to be efficient. This generates sequence blocks in the production plan. Now suppose that the 20th phase requires additional preparation time when the object being produced has special requirements. Phase 20 manages to keep up the pace if it doesn't receive too many consecutive special requests, otherwise it slows down drastically. This creates the need to fragment the production of objects with given characteristics as much as possible. What I have proposed is a formalization of this problem.

Recently, I came across the following problem:

Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a "chain" a maximal substring of $S$ of consecutive ones. We define $l_n(S_{s_1,s_2,...,s_k})$ as the number of chains with length $n$, and we denote with $L(S_{s_1,s_2,\dots,s_k})$ the element $(l_1(S_{s_1,s_2,\dots,s_k}),l_2(S_{s_1,s_2,\dots,s_k}),\dots,l_n(S_{s_1,s_2,\dots,s_k}),\dots)\in \mathbb{N}^\mathbb{N}$. We define "partial permutation" of $S_{s_1,s_2,\dots,s_k}$ a string obtained by the concatenation of $z_1, z_2, \dots, z_k$, where each $z_i$ is a string obtained by reordering the characters of $s_i$. Finally a partial permutation $Z$ of $S_{s_1,s_2,\dots,s_k}$ is called "optimal" if $L(Z)$ is a minimal element in $\mathbb{N}^\mathbb{N}$ with the colexicographic order.

Problem: Find an algorithm that produces an optimal partial permutation of $S_{s_1,s_2,\dots,s_k}$

Example: If $s_1=1, s_2=110, s_3=00010, s_4=100011, s_5=110$, an optimal partial permutation is $Z=1*011*00010*101010*101$ since $L(Z)=(7,1,0,0,\dots)$, and we cannot produce any string without a chain of length $2$ (because of $s_1$ and $s_2$)

I have some ideas to produce "good" partial permutation, but those are not always optimal. Another idea I got is to collapse string based on their number of 0s and 1s: for example every string with $n\geq2$ zeros and $n+1$ ones can always be collapsed to $101$ or $110$ or $011$ or $01110$. Then we create the optimal partial permutation reasoning on the collapsed string, but this is still far from being an algorithm.

I'm not sure if this problem is known; however, any references to articles dealing with this problem or similar ones are welcome.

EDIT: Someone asked me where this problem comes from. The question arises from practical reasons for optimizing production plans. Suppose you have a production chain structured in 30 phases. Each phase must have the same duration as all the others to ensure smooth progress in the production process. Suppose that phases 10, 11 and 12 need to produce similar objects (for example of the same color) to be efficient. This generates sequence blocks in the production plan. Now suppose that the 20th phase requires additional preparation time when the object being produced has special requirements. Phase 20 manages to keep up the pace if it doesn't receive too many consecutive special requests, otherwise it slows down drastically. This creates the need to fragment the production of objects with given characteristics as much as possible. What I have proposed is a formalization of this problem.

Recently, I came across the following problem:

Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a "chain" a maximal substring of $S$ of consecutive ones. We define $l_n(S_{s_1,s_2,...,s_k})$ as the number of chain with lenght $n$, and we denote with $L(S_{s_1,s_2,\dots,s_k})$ the element $(l_1(S_{s_1,s_2,\dots,s_k}),l_2(S_{s_1,s_2,\dots,s_k}),\dots,l_n(S_{s_1,s_2,\dots,s_k}),\dots)\in \mathbb{N}^\mathbb{N}$. We define "partial permutation" of $S_{s_1,s_2,\dots,s_k}$ a string obtained by the concatenation of $z_1, z_2, \dots, z_k$, where each $z_i$ is a string obtained by reordering the characters of $s_i$. Finally a partial permutation $Z$ of $S_{s_1,s_2,\dots,s_k}$ is called "optimal" if $L(Z)$ is a minimal element in $\mathbb{N}^\mathbb{N}$ with the colexicographic order.

Problem: Find an algorithm that produces an otimal partial permutation of $S_{s_1,s_2,\dots,s_k}$

Example: If $s_1=1, s_2=110, s_3=00010, s_4=100011, s_5=110$, a optimal partial permutation is $Z=1*011*00010*101010*101$ since $L(Z)=(7,1,0,0,\dots)$, and we cannot produce any string without a chain of lenght $2$ (becouse of $s_1$ and $s_2$)

I have some ideas to produce "good" partial permutation, but those are not always optimal. Another idea I got is to collapse string based on their number of 0s and 1s: for example every string with $n>=2$ zeros and $n+1$ ones can always be collapsed to $101$ or $110$ or $011$ or $01110$. Then we create the optimal partial permutation reasoning on the collapsed string, but this is still far from being an algorithm.

I'm not sure if this problem is known; however, any references to articles dealing with this problem or similar ones are welcome.

EDIT: Someone asked me where this problem comes from. The question arises from practical reasons for optimizing production plans. Suppose you have a production chain structured in 30 phases. Each phase must have the same duration as all the others to ensure smooth progress in the production process. Suppose that phases 10, 11 and 12 need to produce similar objects (for example of the same color) to be efficient. This generates sequence blocks in the production plan. Now suppose that the 20th phase requires additional preparation time when the object being produced has special requirements. Phase 20 manages to keep up the pace if it doesn't receive too many consecutive special requests, otherwise it slows down drastically. This creates the need to fragment the production of objects with given characteristics as much as possible. What I have proposed is a formalization of this problem.

Recently, I came across the following problem:

Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a "chain" a maximal substring of $S$ of consecutive ones. We define $l_n(S_{s_1,s_2,...,s_k})$ as the number of chain with lenght $n$, and we denote with $L(S_{s_1,s_2,\dots,s_k})$ the element $(l_1(S_{s_1,s_2,\dots,s_k}),l_2(S_{s_1,s_2,\dots,s_k}),\dots,l_n(S_{s_1,s_2,\dots,s_k}),\dots)\in \mathbb{N}^\mathbb{N}$. We define "partial permutation" of $S_{s_1,s_2,\dots,s_k}$ a string obtained by the concatenation of $z_1, z_2, \dots, z_k$, where each $z_i$ is a string obtained by reordering the characters of $s_i$. Finally a partial permutation $Z$ of $S_{s_1,s_2,\dots,s_k}$ is called "optimal" if $L(Z)$ is a minimal element in $\mathbb{N}^\mathbb{N}$ with the colexicographic order.

Problem: Find an algorithm that produces an otimal partial permutation of $S_{s_1,s_2,\dots,s_k}$

Example: If $s_1=1, s_2=110, s_3=00010, s_4=100011, s_5=110$, a optimal partial permutation is $Z=1*011*00010*101010*101$ since $L(Z)=(7,1,0,0,\dots)$, and we cannot produce any string without a chain of lenght $2$ (becouse of $s_1$ and $s_2$)

I have some ideas to produce "good" partial permutation, but those are not always optimal. Another idea I got is to collapse string based on their number of 0s and 1s: for example every string with $n\geq2$ zeros and $n+1$ ones can always be collapsed to $101$ or $110$ or $011$ or $01110$. Then we create the optimal partial permutation reasoning on the collapsed string, but this is still far from being an algorithm.

I'm not sure if this problem is known; however, any references to articles dealing with this problem or similar ones are welcome.

EDIT: Someone asked me where this problem comes from. The question arises from practical reasons for optimizing production plans. Suppose you have a production chain structured in 30 phases. Each phase must have the same duration as all the others to ensure smooth progress in the production process. Suppose that phases 10, 11 and 12 need to produce similar objects (for example of the same color) to be efficient. This generates sequence blocks in the production plan. Now suppose that the 20th phase requires additional preparation time when the object being produced has special requirements. Phase 20 manages to keep up the pace if it doesn't receive too many consecutive special requests, otherwise it slows down drastically. This creates the need to fragment the production of objects with given characteristics as much as possible. What I have proposed is a formalization of this problem.

Recently, I came across the following problem:

Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a "chain" a maximal substring of $S$ of consecutive ones. We define $l_n(S_{s_1,s_2,...,s_k})$ as the number of chain with lenght $n$, and we denote with $L(S_{s_1,s_2,\dots,s_k})$ the element $(l_1(S_{s_1,s_2,\dots,s_k}),l_2(S_{s_1,s_2,\dots,s_k}),\dots,l_n(S_{s_1,s_2,\dots,s_k}),\dots)\in \mathbb{N}^\mathbb{N}$. We define "partial permutation" of $S_{s_1,s_2,\dots,s_k}$ a string obtained by the concatenation of $z_1, z_2, \dots, z_k$, where each $z_i$ is a string obtained by reordering the characters of $s_i$. Finally a partial permutation $Z$ of $S_{s_1,s_2,\dots,s_k}$ is called "optimal" if $L(Z)$ is a minimal element in $\mathbb{N}^\mathbb{N}$ with the colexicographic order.

Problem: Find an algorithm that produces an otimal partial permutation of $S_{s_1,s_2,\dots,s_k}$

Example: If $s_1=1, s_2=110, s_3=00010, s_4=100011, s_5=110$, a optimal partial permutation is $Z=1*011*00010*101010*101$ since $L(Z)=(7,1,0,0,\dots)$, and we cannot produce any string without a chain of lenght $2$ (becouse of $s_1$ and $s_2$)

I have some ideas to produce "good" partial permutation, but those are not always optimal. Another idea I got is to collapse string based on their number of 0s and 1s: for example every string with $n>=2$ zeros and $n+1$ ones can always be collapsed to $101$ or $110$ or $011$ or $01110$. Then we create the optimal partial permutation reasoning on the collapsed string, but this is still far from being an algorithm.

I'm not sure if this problem is known; however, any references to articles dealing with this problem or similar ones are welcome.

Recently, I came across the following problem:

Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a "chain" a maximal substring of $S$ of consecutive ones. We define $l_n(S_{s_1,s_2,...,s_k})$ as the number of chain with lenght $n$, and we denote with $L(S_{s_1,s_2,\dots,s_k})$ the element $(l_1(S_{s_1,s_2,\dots,s_k}),l_2(S_{s_1,s_2,\dots,s_k}),\dots,l_n(S_{s_1,s_2,\dots,s_k}),\dots)\in \mathbb{N}^\mathbb{N}$. We define "partial permutation" of $S_{s_1,s_2,\dots,s_k}$ a string obtained by the concatenation of $z_1, z_2, \dots, z_k$, where each $z_i$ is a string obtained by reordering the characters of $s_i$. Finally a partial permutation $Z$ of $S_{s_1,s_2,\dots,s_k}$ is called "optimal" if $L(Z)$ is a minimal element in $\mathbb{N}^\mathbb{N}$ with the colexicographic order.

Problem: Find an algorithm that produces an otimal partial permutation of $S_{s_1,s_2,\dots,s_k}$

Example: If $s_1=1, s_2=110, s_3=00010, s_4=100011, s_5=110$, a optimal partial permutation is $Z=1*011*00010*101010*101$ since $L(Z)=(7,1,0,0,\dots)$, and we cannot produce any string without a chain of lenght $2$ (becouse of $s_1$ and $s_2$)

I have some ideas to produce "good" partial permutation, but those are not always optimal. Another idea I got is to collapse string based on their number of 0s and 1s: for example every string with $n>=2$ zeros and $n+1$ ones can always be collapsed to $101$ or $110$ or $011$ or $01110$. Then we create the optimal partial permutation reasoning on the collapsed string, but this is still far from being an algorithm.

I'm not sure if this problem is known; however, any references to articles dealing with this problem or similar ones are welcome.

EDIT: Someone asked me where this problem comes from. The question arises from practical reasons for optimizing production plans. Suppose you have a production chain structured in 30 phases. Each phase must have the same duration as all the others to ensure smooth progress in the production process. Suppose that phases 10, 11 and 12 need to produce similar objects (for example of the same color) to be efficient. This generates sequence blocks in the production plan. Now suppose that the 20th phase requires additional preparation time when the object being produced has special requirements. Phase 20 manages to keep up the pace if it doesn't receive too many consecutive special requests, otherwise it slows down drastically. This creates the need to fragment the production of objects with given characteristics as much as possible. What I have proposed is a formalization of this problem.