从一组 n 个元素中找到大小为 r 的唯一集合，只有 1 个大小的子集是共同的
Find unqiue sets of size r from a set of n elements with only 1 size subsets in common
从 n 个元素中找到大小为 r 的唯一集合，使得大小大于 1 的子集在同一顺序中不常见。其中 r 小于 n.
对于 n=10 和 r=5，我能够找到 n 个唯一的集合，它们只有大小为 1 的子集是共同的。即 {1,3} 仅在该顺序的第一组中。
1 3 6 0 5
2 4 7 1 6
3 5 8 2 7
4 6 9 3 8
5 7 0 4 9
6 8 1 5 0
7 9 2 6 1
8 0 3 7 2
9 1 4 8 3
0 2 5 9 4
另一个解决方案
1 4 9 6 5
2 5 0 7 6
3 6 1 8 7
4 7 2 9 8
5 8 3 0 9
6 9 4 1 0
7 0 5 2 1
8 1 6 3 2
9 2 7 4 3
0 3 8 5 4
在一个解中似乎只有 n 个这样的集合是可能的。
如何从数学上证明这一点？
存在多少这样的解决方案，找到所有这些解决方案的算法是什么？
能否将此算法和证明扩展为包含大小为 2（或 p，前提是 p 小于 r）的公共子集。
这是一个已知问题并且可以通过编程方式解决吗？
我试图搜索 http://en.wikipedia.org/wiki/Fano_plane 似乎相关，但我不确定。
首先：据我从您的示例和评论中了解到，您指的不是集合（无序）而是列表（有序）。
解决方案中并不总是 n 个大小为 r 的列表。
例如。 n = 3、r = 2
1 2
1 3
2 1
2 3
3 1
3 2
这是一个包含 n⋅(n-1) = 3⋅2 = 6 个大小为 r 的列表的解决方案。
您总共有 n⋅(n-1) 对元素。每个 r 元素列表包含 r-1（重叠）对，因此不同 r 元素列表的理论最大值为 n⋅(n-1)/(r-1)。
具有 r 个元素列表的最大数量的解决方案数量（短最大解决方案）受 n⋅(n-1)/(r-1) over m (binomial coefficent) 的限制，其中 m是最大解决方案中的列表数。
在示例中，您看到有一个使用所有 6 个可能列表的最大解决方案，因此只有一个最大解决方案。
该示例还表明可以达到理论界限。
如果您为 n 和 r 使用更大的数字，则可能无法达到此限制。
查找所有内容的算法是使用回溯的枚举算法。只需列出所有可能的对并构建列表。如果您只对一个最大解感兴趣，可能存在更智能的算法。
显然，你的两个解法都违反了问题条件，第一个解法在第一行和第六行重复了1和5的序列，第二个解法在第二行和第九行重复了2和7的序列, 但还是很有意思。
我创建了这段代码来实现您正在寻找的算法，希望这不是浪费我的时间。
这足以证明问题可以通过编程方式解决。
该算法包含三个重要的方法。
order_accepted(ArrayList reslist, int c)
搜索到目前为止我们得到的列表，并且 returns 在这些先前生成的列表中的列表（我们正在构建的）的任何元素之后发生 c 时为 false。
buildlist(ArrayList reslist, int siz_r, int[] arr)
要在不违反我们条件的情况下建立列表，当然是用前面的方法来检查了。
lists_start_with(int c, int siz_r, int[] arr)
我们用它来避免丢失以相同数字开头的列表，我们应该这样做，否则我们将不会得到超过一个以任何元素开头的列表（如果存在的话），我们不能得到两个。
build_solution(int[] arr, int siz_r)
您需要此函数为每个输入数字调用前面的方法，以获取所有以它开头的列表并将它们添加到解决方案中。
要获得解决方案，请在 main 方法中设置输入数组 a 和大小 r，如：
ag.build_solution(new int[]{1,2,3,....},r=..);
解决方案：
a={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}, r=17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
14 13 12 11 10 9 8 7 6 5 4 3 2 1 18 19 20
a={1,2,3,4,5}, r=4
1 2 3 4
3 2 1 5
a={1,2,3,4,5,6,7,8,9}, r=4
1 2 3 4
1 5 6 7
2 1 8 9
2 7 6 5
3 5 8 1
3 6 9 2
4 5 9 3
4 7 8 2
7 9 4 1
a={1,2,3,4,5,6,7,8,9}, r=3
1 2 3
1 4 5
1 6 7
1 8 9
2 4 1
2 5 6
2 7 8
3 2 9
3 4 6
3 5 1
3 8 7
4 7 2
4 8 3
5 4 9
5 7 3
5 8 2
6 8 1
6 9 2
7 6 4
7 9 1
8 6 5
9 6 3
9 7 5
9 8 4
a={1,2,3,4,5,6,7,8,9}, r=6
1 2 3 4 5 6
3 2 1 7 8 9
5 4 9 8 7 1
代码：
Class算法:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Alg {
public static List<Object> solut = new ArrayList();
@SuppressWarnings("rawtypes")
public boolean order_accepted(ArrayList reslist, int c) {
boolean result = true;
if ((solut != null) && (solut.size() > 0)) {
Iterator iter = solut.iterator();
// for every list in this solution
while (iter.hasNext()) {
ArrayList temp = (ArrayList) iter.next();
if (temp != null && temp.size() > 0)
// for every element in our current list
for (int el = 0; el < reslist.size(); el++)
// for every element in this list of our solution
for (int j = 0; j < temp.size(); j++)
if (temp.get(j).equals(reslist.get(el))) {
// start looking for c in this list of our
// solution
for (int k = j; k < temp.size(); k++) {
if (temp.get(k).equals(c)) // if you find c
// then it
// is after; so will not
// be after any more;
// drop c.
return false;
}
break;
}
}
}
return result;
}
public boolean is_in_list(int c, ArrayList lst) {
boolean res = false;
if (lst != null)
for (int i = 0; i < lst.size(); i++)
if ((Integer) lst.get(i) == c) {
res = true;
break;
}
return res;
}
public ArrayList copylist(ArrayList lst) {
ArrayList res = null;
if (lst != null) {
res = new ArrayList();
for (int i = 0; i < lst.size(); i++) {
res.add(lst.get(i));
}
}
return res;
}
// we call this method after we set the first element of the list and
// (recursively),
// to get the next (r-1) elements from the input array (arr).
@SuppressWarnings("unchecked")
public boolean buildlist(ArrayList reslist, int siz_r, int[] arr) {
boolean full = false;// this variable determine whether we added an
// element to this reslist or no available
// element found
if (reslist.size() < siz_r) {
for (int i = 0; i < arr.length; i++) {
// if arr[i] is not in the current list and,
// its order (after) every element is accepted (never happened
// in the solution).
if (!is_in_list(arr[i], reslist)
&& order_accepted(reslist, arr[i])) {
reslist.add(arr[i]);
if (reslist.size() == siz_r)// list is full
{
full = true;
break;
}
else
{
//if fill with others is possible
ArrayList tmp=copylist(reslist);
if(buildlist(tmp,siz_r,arr))
{
return buildlist(reslist,siz_r,arr);
}
//else remove this element
//and continue searching for others.
else
{
reslist.remove(reslist.size()-1);
}
}
}// endif
}// endfor
return full;
} else
return true;
}
public void listes_start_with(int c, int siz_r, int[] arr) {
// Don't start with other numbers when you still have other listes start
// withe the same number, Example:
// arr{1,2,3,4,5} r=3 => (1) 2 3; (1) 4 5; 2 4 1; ...
// Note that only sub set of size One could be repeated in the same
// order (relatively); ({12}3; {12}4 are wrong listes).
boolean possible = true;// the possibility of finding other listes start
// with c by the result of buildlist method.
while (possible) {
ArrayList ls = new ArrayList();
ls.add(c);
if (c == 2) {
int x = 0;
x += 1;
}
if (buildlist(ls, siz_r, arr))
solut.add(ls);
else
possible = false;
}
}
public void build_solution(int[] arr, int siz_r) {
for (int i = 0; i < arr.length; i++) {
listes_start_with(arr[i], siz_r, arr);
}
}
@SuppressWarnings("rawtypes")
public void showsolution() {
for (int i = 0; i < solut.size(); i++) {
ArrayList temp = (ArrayList) solut.get(i);
if (temp != null && temp.size() > 0) {
for (int j = 0; j < temp.size(); j++) {
System.out.print(temp.get(j) + " ");
}
}
System.out.println("");
}
}
}
主要Class
public class Mclass {
public static void main(String args[])
{
Alg ag=new Alg();
ag.build_solution(new int[]{1,2,3,4,5,6,7,8,9},3);
ag.showsolution();
}
}
扩展算法以将所有公共子集包含在一个解决方案中，我认为最好为此创建一个单独的子集。
我无法从数学上证明解决方案中可能列表的数量。
甚至解决方案的全部数量，因为我只知道当您对输入数组进行不同排序时，您会得到（在此算法中）不同的解决方案。
从 n 个元素中找到大小为 r 的唯一集合，使得大小大于 1 的子集在同一顺序中不常见。其中 r 小于 n.
对于 n=10 和 r=5，我能够找到 n 个唯一的集合，它们只有大小为 1 的子集是共同的。即 {1,3} 仅在该顺序的第一组中。
1 3 6 0 5
2 4 7 1 6
3 5 8 2 7
4 6 9 3 8
5 7 0 4 9
6 8 1 5 0
7 9 2 6 1
8 0 3 7 2
9 1 4 8 3
0 2 5 9 4
另一个解决方案
1 4 9 6 5
2 5 0 7 6
3 6 1 8 7
4 7 2 9 8
5 8 3 0 9
6 9 4 1 0
7 0 5 2 1
8 1 6 3 2
9 2 7 4 3
0 3 8 5 4
在一个解中似乎只有 n 个这样的集合是可能的。 如何从数学上证明这一点？
存在多少这样的解决方案，找到所有这些解决方案的算法是什么？
能否将此算法和证明扩展为包含大小为 2（或 p，前提是 p 小于 r）的公共子集。
这是一个已知问题并且可以通过编程方式解决吗？
我试图搜索 http://en.wikipedia.org/wiki/Fano_plane 似乎相关，但我不确定。
首先：据我从您的示例和评论中了解到，您指的不是集合（无序）而是列表（有序）。
解决方案中并不总是 n 个大小为 r 的列表。
例如。 n = 3、r = 2
1 2
1 3
2 1
2 3
3 1
3 2
这是一个包含 n⋅(n-1) = 3⋅2 = 6 个大小为 r 的列表的解决方案。
您总共有 n⋅(n-1) 对元素。每个 r 元素列表包含 r-1（重叠）对，因此不同 r 元素列表的理论最大值为 n⋅(n-1)/(r-1)。
具有 r 个元素列表的最大数量的解决方案数量（短最大解决方案）受 n⋅(n-1)/(r-1) over m (binomial coefficent) 的限制，其中 m是最大解决方案中的列表数。
在示例中，您看到有一个使用所有 6 个可能列表的最大解决方案，因此只有一个最大解决方案。
该示例还表明可以达到理论界限。
如果您为 n 和 r 使用更大的数字，则可能无法达到此限制。
查找所有内容的算法是使用回溯的枚举算法。只需列出所有可能的对并构建列表。如果您只对一个最大解感兴趣，可能存在更智能的算法。
显然，你的两个解法都违反了问题条件，第一个解法在第一行和第六行重复了1和5的序列，第二个解法在第二行和第九行重复了2和7的序列, 但还是很有意思。
我创建了这段代码来实现您正在寻找的算法，希望这不是浪费我的时间。 这足以证明问题可以通过编程方式解决。
该算法包含三个重要的方法。
order_accepted(ArrayList reslist, int c)
搜索到目前为止我们得到的列表，并且 returns 在这些先前生成的列表中的列表（我们正在构建的）的任何元素之后发生 c 时为 false。
buildlist(ArrayList reslist, int siz_r, int[] arr)
要在不违反我们条件的情况下建立列表，当然是用前面的方法来检查了。
lists_start_with(int c, int siz_r, int[] arr)
我们用它来避免丢失以相同数字开头的列表，我们应该这样做，否则我们将不会得到超过一个以任何元素开头的列表（如果存在的话），我们不能得到两个。
build_solution(int[] arr, int siz_r)
您需要此函数为每个输入数字调用前面的方法，以获取所有以它开头的列表并将它们添加到解决方案中。
要获得解决方案，请在 main 方法中设置输入数组 a 和大小 r，如：
ag.build_solution(new int[]{1,2,3,....},r=..);
解决方案：
a={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}, r=17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
14 13 12 11 10 9 8 7 6 5 4 3 2 1 18 19 20
a={1,2,3,4,5}, r=4
1 2 3 4
3 2 1 5
a={1,2,3,4,5,6,7,8,9}, r=4
1 2 3 4
1 5 6 7
2 1 8 9
2 7 6 5
3 5 8 1
3 6 9 2
4 5 9 3
4 7 8 2
7 9 4 1
a={1,2,3,4,5,6,7,8,9}, r=3
1 2 3
1 4 5
1 6 7
1 8 9
2 4 1
2 5 6
2 7 8
3 2 9
3 4 6
3 5 1
3 8 7
4 7 2
4 8 3
5 4 9
5 7 3
5 8 2
6 8 1
6 9 2
7 6 4
7 9 1
8 6 5
9 6 3
9 7 5
9 8 4
a={1,2,3,4,5,6,7,8,9}, r=6
1 2 3 4 5 6
3 2 1 7 8 9
5 4 9 8 7 1
代码：
Class算法:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Alg {
public static List<Object> solut = new ArrayList();
@SuppressWarnings("rawtypes")
public boolean order_accepted(ArrayList reslist, int c) {
boolean result = true;
if ((solut != null) && (solut.size() > 0)) {
Iterator iter = solut.iterator();
// for every list in this solution
while (iter.hasNext()) {
ArrayList temp = (ArrayList) iter.next();
if (temp != null && temp.size() > 0)
// for every element in our current list
for (int el = 0; el < reslist.size(); el++)
// for every element in this list of our solution
for (int j = 0; j < temp.size(); j++)
if (temp.get(j).equals(reslist.get(el))) {
// start looking for c in this list of our
// solution
for (int k = j; k < temp.size(); k++) {
if (temp.get(k).equals(c)) // if you find c
// then it
// is after; so will not
// be after any more;
// drop c.
return false;
}
break;
}
}
}
return result;
}
public boolean is_in_list(int c, ArrayList lst) {
boolean res = false;
if (lst != null)
for (int i = 0; i < lst.size(); i++)
if ((Integer) lst.get(i) == c) {
res = true;
break;
}
return res;
}
public ArrayList copylist(ArrayList lst) {
ArrayList res = null;
if (lst != null) {
res = new ArrayList();
for (int i = 0; i < lst.size(); i++) {
res.add(lst.get(i));
}
}
return res;
}
// we call this method after we set the first element of the list and
// (recursively),
// to get the next (r-1) elements from the input array (arr).
@SuppressWarnings("unchecked")
public boolean buildlist(ArrayList reslist, int siz_r, int[] arr) {
boolean full = false;// this variable determine whether we added an
// element to this reslist or no available
// element found
if (reslist.size() < siz_r) {
for (int i = 0; i < arr.length; i++) {
// if arr[i] is not in the current list and,
// its order (after) every element is accepted (never happened
// in the solution).
if (!is_in_list(arr[i], reslist)
&& order_accepted(reslist, arr[i])) {
reslist.add(arr[i]);
if (reslist.size() == siz_r)// list is full
{
full = true;
break;
}
else
{
//if fill with others is possible
ArrayList tmp=copylist(reslist);
if(buildlist(tmp,siz_r,arr))
{
return buildlist(reslist,siz_r,arr);
}
//else remove this element
//and continue searching for others.
else
{
reslist.remove(reslist.size()-1);
}
}
}// endif
}// endfor
return full;
} else
return true;
}
public void listes_start_with(int c, int siz_r, int[] arr) {
// Don't start with other numbers when you still have other listes start
// withe the same number, Example:
// arr{1,2,3,4,5} r=3 => (1) 2 3; (1) 4 5; 2 4 1; ...
// Note that only sub set of size One could be repeated in the same
// order (relatively); ({12}3; {12}4 are wrong listes).
boolean possible = true;// the possibility of finding other listes start
// with c by the result of buildlist method.
while (possible) {
ArrayList ls = new ArrayList();
ls.add(c);
if (c == 2) {
int x = 0;
x += 1;
}
if (buildlist(ls, siz_r, arr))
solut.add(ls);
else
possible = false;
}
}
public void build_solution(int[] arr, int siz_r) {
for (int i = 0; i < arr.length; i++) {
listes_start_with(arr[i], siz_r, arr);
}
}
@SuppressWarnings("rawtypes")
public void showsolution() {
for (int i = 0; i < solut.size(); i++) {
ArrayList temp = (ArrayList) solut.get(i);
if (temp != null && temp.size() > 0) {
for (int j = 0; j < temp.size(); j++) {
System.out.print(temp.get(j) + " ");
}
}
System.out.println("");
}
}
}
主要Class
public class Mclass {
public static void main(String args[])
{
Alg ag=new Alg();
ag.build_solution(new int[]{1,2,3,4,5,6,7,8,9},3);
ag.showsolution();
}
}
扩展算法以将所有公共子集包含在一个解决方案中，我认为最好为此创建一个单独的子集。
我无法从数学上证明解决方案中可能列表的数量。 甚至解决方案的全部数量，因为我只知道当您对输入数组进行不同排序时，您会得到（在此算法中）不同的解决方案。