مساله:
در ویکی پدیا https://en.wikipedia.org/wiki/Partition_(number_theory)
در نظریه اعداد و ترکیب، تقسیم بندی یک عدد صحیح مثبت ، که تقسیم بندی عدد صحیح نیز نامیده می شود، راهی برای نوشتن n به عنوان مجموع اعداد صحیح مثبت است. دو مجموع که فقط در ترتیب جمع بندی آنها متفاوت است ، یک تقسیم بندی یکسان محسوب می شوند.
به عنوان مثال، 4 را می توان به پنج روش مجزا تقسیم بندی کرد:
4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
ما می توانیم بنویسیم:
enum(4) -> [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] و
enum(5) -> [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]].
تعداد قسمت ها در تقسیم بندی به سرعت زیاد می شوند. برای مثال برای n=50 تعداد 204226 تقسیم بندی وجود دارد. یا برای 80 تعداد 15,796,476 تقسیم بندی وجود دارد. تست پاسخ ها با آرایه هایی با این اندازه بسیار طولانی خواهد بود. بنابراین وظیفه ما به شرح زیر است:
۱. n که به صورت عدد صحیح و (n integer, 1 <= n <= 50) برای محاسبه enum(n) داده می شود. ما چیزی شبیه به این را بدست خواهیم آورد:
enum(n) -> [[n],[n-1,1],[n-2,2],...,[1,1,...,1]]
(ترتیب آرایه ها و زیر آرایه ها مهم نیست). این قسمت چک نمی شود.
2. برای هر زیر آرایه enum (n) نتیجه آن را محاسبه کنید. اگر n = 5 باشد پس از حذف موارد تکراری و مرتب سازی باید بدست آوریم:
prod(5) -> [1,2,3,4,5,6]
prod(8) -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 18]
اگر n = 40 prod (n) دارای طول 2699 باشد ، بنابراین آزمایش ها چنین آرایه هایی را تأیید نمی کنند. در عوض وظیفه شماره 3 ما این است:
۳. محدوده ، میانگین و میانه prod (n) را به شکل زیر بازگردانید (مثال برای n = 5):
“Range: 5 Average: 3.50 Median: 3.50”
Range یک عدد صحیح است ، Average و Median اعداد اعشاری هستند که به دو رقم اعشار، گرد می شوند (“.2f” در برخی از زبانها).
نکته ها:
Range: تفاوت بین بالاترین و کمترین مقادیر.
Mean or Average: برای محاسبه میانگین ، همه اعداد یک مجموعه را با هم جمع کرده و سپس مجموع را بر تعداد کل اعداد تقسیم کنید.
Median: میانگین عددی است که نیمه بالای نمونه داده را از نیمه پایینی جدا می کند.
توجه:
سعی کنید برنامه خود را بهینه کنید تا از اتمام زمان جلوگیری شود.
From wikipedia https://en.wikipedia.org/wiki/Partition_(number_theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition.
For example, 4 can be partitioned in five distinct ways:
4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
We can write:
enum(4) -> [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] and
enum(5) -> [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]].
The number of parts in a partition grows very fast. For n = 50 number of parts is 204226, for 80 it is 15,796,476 It would be too long to tests answers with arrays of such size. So our task is the following:
1 – n being given (n integer, 1 <= n <= 50) calculate enum(n) ie the partition of n. We will obtain something like that:enum(n) -> [[n],[n-1,1],[n-2,2],...,[1,1,...,1]] (order of array and sub-arrays doesn’t matter). This part is not tested.
2 – For each sub-array of enum(n) calculate its product. If n = 5 we’ll obtain after removing duplicates and sorting:
prod(5) -> [1,2,3,4,5,6]
prod(8) -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 16, 18]
If n = 40 prod(n) has a length of 2699 hence the tests will not verify such arrays. Instead our task number 3 is:
3 – return the range, the average and the median of prod(n) in the following form (example for n = 5):
"Range: 5 Average: 3.50 Median: 3.50"
Range is an integer, Average and Median are float numbers rounded to two decimal places (“.2f” in some languages).
Notes:
Range : difference between the highest and lowest values.
Mean or Average : To calculate mean, add together all of the numbers in a set and then divide the sum by the total count of numbers.
Median : The median is the number separating the higher half of a data sample from the lower half. (https://en.wikipedia.org/wiki/Median)
Hints:
Try to optimize your program to avoid timing out.
Memoization can be helpful but it is not mandatory for being successful.
راه حل ها:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class IntPart {
public static String part(long n) {
List<List<Integer>> list = partition((int) n);
List<Integer> prodList = new ArrayList<Integer>();
for (List<Integer> comb : list) {
int multiply = comb.stream().reduce(1, (a, b) -> a * b);
if (!prodList.contains(multiply))
prodList.add(multiply);
}
Collections.sort(prodList);
Integer range = prodList.get(prodList.size() - 1) - prodList.get(0);
double average = prodList.stream().mapToDouble(d -> d).average().orElse(0.0);
double median = 0d;
if (prodList.size() % 2 == 0)
median = ((double)prodList.get(prodList.size()/2) + (double)prodList.get(prodList.size()/2 - 1))/2;
else
median = (double) prodList.get(prodList.size()/2);
return "Range: " + range + " Average: " + String.format("%.2f", average) + " Median: " + String.format("%.2f", median);
}
public static List<List<Integer>> partition(int n) {
List<List<Integer>> list = new ArrayList<>();
partition(n, n, "", list, new ArrayList<Integer>());
return list;
}
public static void partition(int i, int max, String indent, List<List<Integer>> master, List<Integer> holder) {
if (i == 0) {
master.add(holder);
}
for (int j = Math.min(max, i); j >= 1; j--) {
ArrayList<Integer> temp = new ArrayList<>(holder);
temp.add(j);
partition(i - j, j, indent + " ", master, temp);
}
}
}import java.util.HashMap;
import java.util.Map;
import java.util.stream.LongStream;
import java.util.stream.Stream;
public class IntPart {
private static Map<Long, long[][]> partCache = new HashMap<>();
public static String part(long n) {
// your code
long[] prod = Stream.of(getPart(n))
.map(IntPart::multiple)
.mapToLong(l -> l)
.sorted()
.distinct()
.toArray();
long range = prod[prod.length - 1] - prod[0];
double average = 1.0 * LongStream.of(prod).sum() / prod.length;
double median = prod.length % 2 == 0 ? (prod[prod.length / 2 - 1] + prod[prod.length / 2]) / 2.0 : prod[prod.length / 2];
return String.format("Range: %d Average: %.2f Median: %.2f", range, average, median);
}
private static long multiple(long[] ls) {
long result = 1;
for (long l: ls) {
result *= l;
}
return result;
}
private static long[][] getPart(long n) {
if (partCache.get(n) != null) {
return partCache.get(n);
}
long[][] result =
LongStream.rangeClosed(1, n)
.boxed()
.flatMap(m -> getMStartPart(n, m))
.toArray(long[][]::new);
partCache.put(n, result);
return result;
}
private static Stream<long[]> getMStartPart(long n, long m) {
if (n == m) {
return Stream.of(new long[] {n});
} else {
return Stream.of(getPart(n - m))
.filter(ls -> ls[0] <= m)
.map(ls -> concat(m, ls));
}
}
private static long[] concat(long l, long[] ls) {
long[] result = new long[ls.length + 1];
result[0] = l;
System.arraycopy(ls, 0, result, 1, ls.length);
return result;
}
}
import java.util.*;
import java.util.stream.LongStream;
public class IntPart {
private static void subPartition(long n, long bound, long muliplier, Set<Long> products) {
products.add(muliplier); // n times 1
if (bound >= n) {
products.add(muliplier * n); // 1 time n
bound = n - 1;
}
for (long i = 2; i <= bound; i++)
subPartition(n - i, i, muliplier * i, products);
}
public static String part(long n) {
Set<Long> prodSet = new HashSet<>();
subPartition(n, n, 1, prodSet);
long[] products = prodSet.stream().sorted().mapToLong(Long::longValue).toArray();
LongSummaryStatistics stat = LongStream.of(products).summaryStatistics();
int k = products.length;
int k2 = k >> 1;
double median = (k & 1) == 0 ? ((double)products[k2 - 1] + products[k2]) / 2.0
: products[k2];
return String.format("Range: %d Average: %.2f Median: %.2f", stat.getMax() - stat.getMin(),
stat.getAverage(), median);
}
}
import java.util.TreeSet;
import java.util.Collections;
import java.util.ArrayList;
public class IntPart {
private static void calc(long maxVal, long leftVal, long prodVal){
prodSets.add(prodVal);
for(long x=2;x<=maxVal && x<=leftVal;++x)
calc(x,leftVal-x, prodVal *x);
}
public static String part(long n) {
prodSets = new TreeSet<>();
calc(n,n,1);
ArrayList<Long> prodArr = new ArrayList<>(prodSets);
int length = prodArr.size();
String retVal = String.format("Range: %d ", (prodArr.get(length -1) - prodArr.get(0)));
long sumVal = 0;
for(Long numVal : prodArr)
sumVal = sumVal + numVal;
retVal = retVal + String.format("Average: %.2f ", (double) sumVal / length);
double medianVal = prodArr.get(length / 2);
if(length % 2 == 0)
medianVal = (medianVal + prodArr.get(length / 2 -1)) / 2;
retVal = retVal + String.format("Median: %.2f", medianVal);
return retVal;
}
private static TreeSet<Long> prodSets;
}
