求一算法！！

Question

算法要求描述如下：
给定一个集合S={a1,a2,…,an},其中ai都是集合。任意一个自然数N，求用S中的元素ai来表示N的所有方法。也就是说每种方法要使 a1，a2，…，an中的元素之和等于N，且要求ai中的元素不超过3。
e.g.   S={a1,a2,a3,a4}, |ai|=i , 即a2就是拥有2个元素的集合，S是包含1个，2个，3个，4个元素集合的集合。N=5 ,则将N填入S的方法如下：
       N={1}+{1，1，1，1}
       N={1，1}+{1，1，1}
       N={1}+{2，2}
       N={2}+{1,1,1}
       N={3}+{1,1}
 其余的集合都填0。谢高手解答！！        

Answer 1

"N={1}+{1，1，1，1}"和"且要求ai中的元素不超过3"是不是矛盾了？
｛4｝，｛1｝，｛0｝，｛0，0｝算不算？
｛4｝，｛1｝，｛0，0｝，｛0，0｝算不算？

Answer 2

"且要求ai中的元素不超过3"是指ai中元素的值不超过3?

Answer 3

对，"且要求ai中的元素不超过3"是指ai中元素的值不超过3
应该是，N={1}+{0,0}+{0,0,0}+{1,1,1,1}

Answer 4

要求ai中的元素不超过3,不是指ai的集合大小不超过3，而是指其中的值不超过3

Answer 5

集合是可以有重复元素的
Set集合元素不能重复   但List集合就是行的

Answer 6

import java.util.*; 
public class Test2{
private static ArrayList<Integer[][]> resultArr=new ArrayList<Integer[][]>();
public static void main(String [] args) {
int setSize=4;
int num=5;
int[] result=new int[(1+setSize)*setSize/2];
fun(num,result,0);
printResult();
System.out.println(resultArr.size());
} 

public static void fun(int num,int[] result,int position){
if(position==result.length-1){
if(num==0){
arrayToSet(result);
}
return ;
}
if(num!=0){
for(int i=0;i<=3;i++){
if(num-i>=0){
int temp=result[position];
result[position]=i;
fun(num-i,result,position+1);
result[position]=temp;
//System.out.println(Arrays.toString(result));
}else{
fun(num,result,result.length-1);
}
}

}
}
private static void arrayToSet(int[] result){
Integer[][] aResult=new Integer[4][];
int count=0;
for(int i=0;i<4;i++){
aResult[i]=new Integer[i+1];
for(int j=0;j<=i;j++){
aResult[i][j]=result[count++];
}
}
resultArr.add(aResult);
}
public static void printResult(){
for(Integer[][] one:resultArr){
for(Integer[] line:one){
System.out.print(Arrays.toString(line)+",");
}
System.out.println("\b ");
}
}
}最后一段结果,对不对呢?:
[2],[0, 1],[0, 1, 0],[0, 0, 1, 0]
[2],[0, 1],[1, 0, 0],[0, 0, 1, 0]
[2],[0, 2],[0, 0, 0],[0, 0, 1, 0]
[2],[1, 0],[0, 0, 0],[0, 0, 2, 0]
[2],[1, 0],[0, 0, 0],[0, 1, 1, 0]
[2],[1, 0],[0, 0, 0],[1, 0, 1, 0]
[2],[1, 0],[0, 0, 1],[0, 0, 1, 0]
[2],[1, 0],[0, 1, 0],[0, 0, 1, 0]
[2],[1, 0],[1, 0, 0],[0, 0, 1, 0]
[2],[1, 1],[0, 0, 0],[0, 0, 1, 0]
[2],[2, 0],[0, 0, 0],[0, 0, 1, 0]
[3],[0, 0],[0, 0, 0],[0, 0, 2, 0]
[3],[0, 0],[0, 0, 0],[0, 1, 1, 0]
[3],[0, 0],[0, 0, 0],[1, 0, 1, 0]
[3],[0, 0],[0, 0, 1],[0, 0, 1, 0]
[3],[0, 0],[0, 1, 0],[0, 0, 1, 0]
[3],[0, 0],[1, 0, 0],[0, 0, 1, 0]
[3],[0, 1],[0, 0, 0],[0, 0, 1, 0]
[3],[1, 0],[0, 0, 0],[0, 0, 1, 0]
478

Answer 7

不好意思啊！！我没有把条件说清楚。
集合ai中的元素要相同,并且ai中的元素大小不超过3.
所以就像我举得例子，N=5 ,则将N填入S的方法就只有一下这些： 
       N={1}+{0，0}+{0，0，0}+{1，1，1，1} 
      N={0}+{1，1}+{1，1，1}+{0，0，0，0}
      N={1}+{2，2}+{0，0，0}+{0，0，0，0}
      N={2}+{0，0}+{1，1，1}+{0，0，0，0} 
      N={3}+{1，1}+{0，0，0}+{0，0，0，0} 

Answer 8

lz你可以把你要的算法看成这么一个式子，
N=1a+2b+3c+...+np,
这样楼主应该能够自己写出来了吧。
小想了一下，单纯用循环貌似做不出来，加上迭代就能搞定。

Answer 9

本来a.b.c....p应该写成ai的，这个下标不会写，哈哈。
ai要小于3并且小于n/i，这个是判断条件，其他用程序一个一个加去。

Answer 10

稍改一下程序:
mport java.util.*; 
public class Test2{
private static ArrayList<Integer[][]> resultArr=new ArrayList<Integer[][]>();
public static void main(String [] args) {
int setSize=4;
int num=5;
int[] result=new int[(1+setSize)*setSize/2];
fun(num,result,0,setSize);
printResult();
System.out.println("共有 "+resultArr.size()+"种结果");
} 

public static void fun(int num,int[] result,int numSet,int setSize){
if(numSet==setSize){
if(num==0){
arrayToSet(result);
}
return ;
}
if(num>=0){
for(int i=0;i<=3;i++){
if(num-i*(numSet+1)>=0){
int start=(1+numSet)*numSet/2;
int end=start+numSet+1;
for(int j=start;j<end;j++){
result[j]=i;
}
fun(num-i*(numSet+1),result,numSet+1,setSize);
}
}

}
}
private static void arrayToSet(int[] result){
Integer[][] aResult=new Integer[4][];
int count=0;
for(int i=0;i<4;i++){
aResult[i]=new Integer[i+1];
for(int j=0;j<=i;j++){
aResult[i][j]=result[count++];
}
}
resultArr.add(aResult);
}
public static void printResult(){
for(Integer[][] one:resultArr){
for(Integer[] line:one){
System.out.print(Arrays.toString(line)+",");
}
System.out.println("\b ");
}
}
}
F:\java>java Test2
[0],[1, 1],[1, 1, 1],[0, 0, 0, 0]
[1],[0, 0],[0, 0, 0],[1, 1, 1, 1]
[1],[2, 2],[0, 0, 0],[0, 0, 0, 0]
[2],[0, 0],[1, 1, 1],[0, 0, 0, 0]
[3],[1, 1],[0, 0, 0],[0, 0, 0, 0]
5

Answer 11

再改一下,改为通用的程序:
import java.util.*; 
public class Test2{
private static ArrayList<Integer[][]> resultArr=new ArrayList<Integer[][]>();
public static void main(String [] args) {
int setSize=5;
int num=7;
int[] result=new int[(1+setSize)*setSize/2];
fun(num,result,0,setSize);
System.out.println("N="+num+", |S|="+setSize);
printResult();
System.out.println("共有 "+resultArr.size()+"种结果");
} 

public static void fun(int num,int[] result,int numSet,int setSize){
if(numSet==setSize){
if(num==0){
arrayToSet(result,setSize);
}
return ;
}
if(num>=0){
for(int i=0;i<=3;i++){
if(num-i*(numSet+1)>=0){
int start=(1+numSet)*numSet/2;
int end=start+numSet+1;
for(int j=start;j<end;j++){
result[j]=i;
}
fun(num-i*(numSet+1),result,numSet+1,setSize);
}
}

}
}
private static void arrayToSet(int[] result,int setSize){
Integer[][] aResult=new Integer[setSize][];
int count=0;
for(int i=0;i<setSize;i++){
aResult[i]=new Integer[i+1];
for(int j=0;j<=i;j++){
aResult[i][j]=result[count++];
}
}
resultArr.add(aResult);
}
public static void printResult(){
for(Integer[][] one:resultArr){
for(Integer[] line:one){
System.out.print(Arrays.toString(line)+",");
}
System.out.println("\b ");
}
}
}F:\java>java Test2
N=7, |S|=5
[0],[0, 0],[1, 1, 1],[1, 1, 1, 1],[0, 0, 0, 0, 0]
[0],[1, 1],[0, 0, 0],[0, 0, 0, 0],[1, 1, 1, 1, 1]
[0],[2, 2],[1, 1, 1],[0, 0, 0, 0],[0, 0, 0, 0, 0]
[1],[0, 0],[2, 2, 2],[0, 0, 0, 0],[0, 0, 0, 0, 0]
[1],[1, 1],[0, 0, 0],[1, 1, 1, 1],[0, 0, 0, 0, 0]
[1],[3, 3],[0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0, 0]
[2],[0, 0],[0, 0, 0],[0, 0, 0, 0],[1, 1, 1, 1, 1]
[2],[1, 1],[1, 1, 1],[0, 0, 0, 0],[0, 0, 0, 0, 0]
[3],[0, 0],[0, 0, 0],[1, 1, 1, 1],[0, 0, 0, 0, 0]
[3],[2, 2],[0, 0, 0],[0, 0, 0, 0],[0, 0, 0, 0, 0]
共有 10种结果

Answer 12

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */package fillaxis;
import java.util.*;
/**
 *
 * @author KILLer
 */
public class SolutionGenerator {
    int[] groupNum={1,2,3,4};//每个组的大小
    int[] startIndex={0,1,3,6};//每个组第一个元素的开始下标
    int[] column=new int[10];
    ArrayList<int[]> list=new ArrayList<int[]>();//用于存放结果
     //n填的数，groupIndex组开始下标
    public void genSolution(int n,int groupIndex){
        if(n==0){
            int[] tmp=new int[10];
            System.arraycopy(column, 0, tmp, 0, 10);
            list.add(tmp);
        }
        else if(groupIndex<4){
            for(int i=0;i<=3;i++){
                this.setTable(groupIndex, i);//用i填第groupIndex组
                genSolution(n-groupNum[groupIndex]*i,groupIndex+1);
                this.recoverTable(groupIndex);//恢复该组，用于回溯
            }
        }
    }
    //用num填第groupIndex组
    private void setTable(int groupIndex,int num){
        int endIndex=startIndex[groupIndex]+this.groupNum[groupIndex];
        for(int i=startIndex[groupIndex];i<endIndex;i++)
            this.column[i]=num;
    }
    private void recoverTable(int groupIndex){
        int endIndex=startIndex[groupIndex]+this.groupNum[groupIndex];
        for(int i=startIndex[groupIndex];i<endIndex;i++)
            this.column[i]=0;
    }
    public ArrayList<int[]> getList(){
        return this.list;
    }
         public static void main(String[] a){
        SolutionGenerator sg=new SolutionGenerator();
        sg.genSolution(7, 0);
        ArrayList<int[]> list=sg.getList();
        for(int[] b:list){
            for(int i=0;i<10;i++){
                if(i==0|i==1|i==3|i==6)
                    System.out.print("{ ");
                System.out.print(b[i]+" ");
                if(i==0|i==2|i==5|i==9)
                    System.out.print("}");
            }
            System.out.println();
        }
    }
}
自己写了一个，用了递归回溯的思想。
{ 0 }{ 0 0 }{ 1 1 1 }{ 1 1 1 1 }
{ 0 }{ 2 2 }{ 1 1 1 }{ 0 0 0 0 }
{ 1 }{ 0 0 }{ 2 2 2 }{ 0 0 0 0 }
{ 1 }{ 1 1 }{ 0 0 0 }{ 1 1 1 1 }
{ 1 }{ 3 3 }{ 0 0 0 }{ 0 0 0 0 }
{ 2 }{ 1 1 }{ 1 1 1 }{ 0 0 0 0 }
{ 3 }{ 0 0 }{ 0 0 0 }{ 1 1 1 1 }
{ 3 }{ 2 2 }{ 0 0 0 }{ 0 0 0 0 }