# How to rebuild original data from a histogram?

I have data in the following form. I have a list of values and a list of frequencies that indicate how often each value has occurred.

Example list of values: {5,7,4}

Example list of frequencies: {1,2,3}

I would like to obtain the original data from which such a histogram was generated. Any suggestions on how to do this with Mathematica ?

Example: {5,7,7,4,4,4}

-

## 4 Answers

Without looking at performance, but only on understanding: First, you create a function f which takes a value and a count and which reproduces the value exactly count times. In the simplest case

f[val_, count_] := ConstantArray[val, count]


and you can call f[3,4] to get {3,3,3,3}. Now, you combine your input arrays so that you can call f directly for each pair. For this, you can use MapThread. To create you final result, you have to Flatten the output:

Flatten[MapThread[f, {{5, 7, 4}, {1, 2, 3}}]]


This all can of course be combined into one call

vals = {5, 7, 4};
counts = {1, 2, 3};

Flatten[MapThread[ConstantArray, {vals, counts}]]


or

ConstantArray @@@ Transpose[{vals, counts}] // Flatten


or (to simplify kgulers approach)

Inner[ConstantArray, vals, counts, Join]


and many more

-
 values = RandomSample[Range[100], 5]
(*{72,75,44,25,60}*)
counts = RandomInteger[{1, 5}, 5]
(* {4,3,1,1,1} *)


Inner and Table:

 Inner[Table[#1, {#2}] &, values, counts, Join] (*thanks: Halirutan *)


Inner and ConstantArray:

 Flatten@Inner[ConstantArray, values, counts, List]


both give

 {72, 72, 72, 72, 75, 75, 75, 44, 25, 60}


Update: further variations using Thread, MapIndexed ...

 Table @@@ Thread[{values, List /@ counts}] // Flatten
#1[[Join @@ MapIndexed[Table[First[#2], {#}] &, #2]]] &[values, counts]
Module[{f}, Thread[f[values, List /@ counts]] /. f -> Table // Flatten]

-

### Introduction

This answer is mainly concerned with the performance (speed and memory) of methods that solve the OPs problem. Of course we only care about performance if the data is of some considerable size. In this answer I first generate data, then show some methods to solve the problem and then I compare the timings.

### Generating data: Similarity to data from FactorInteger

Let's generate some data to do timing comparisons with. Let us first realise that there is another setting in which the same problem can occur. Suppose one wants to find a list of all the prime factors of an integer. FactorInteger does almost exactly this job, but instead repeating prime numbers that occur more than once as a factor, it gives the number of the times the factor occurs in the factorisation.

To get from FactorInteger to data that matches this problem, we would have to do

in=10012312312312;
{values, counts} = {sortedUniquePrimes, primeTimes} = Transpose@FactorInteger[in]


However, the length of prime factorisation of a (uniformly) random integer is a bit chaotic. Therefore I make the data corresponding to prime factorisations in a different manner.

Note that there is an extremely small probability that there will be an error in generating the data, in which case you can just execute the code again. The data below is not large enough to justify e.g. creating a library (as we will see being created in one of the methods below), but it is large enough to compare the methods sensibly.

Block[{primes, primeSeeds},
primes = Table[Prime[kkkk], {kkkk, 500000}];
primeSeeds = RandomInteger[{1, 500000}, 2000000];
sortedUniquePrimes =
Take[DeleteDuplicates[Sort[Part[primes, primeSeeds]]], 200000];
primeTimes = RandomInteger[{1, 10}, 200000];
]


### Methods

The fastest thing I could come up with was a function written in C that was linked to the kernel by LibraryLink. A compiled function turned out to be pretty fast as well. I programmed some funky code making use of Span, but that turned out to be slower than Halirutans version. It seems that Span is best used when one only has to change a part of a list.

LibraryLink function

There are three things I can think that may make you want to not execute the following code. One is that if you do not have a C compiler, this is not going to work. Another thing is that I do not clean up the library after creating it, which is probably not a big deal, but still. A third thing is that it may crash the kernel (this version never crashed for me), as it is one of my first programs written for LibraryLink.

Here is the function (in fact the entire file) written in C

#include "WolframLibrary.h"

/* Return the version of Library Link */
DLLEXPORT mint WolframLibrary_getVersion( ) {
return WolframLibraryVersion;
}

/* Initialize Library */
DLLEXPORT int WolframLibrary_initialize( WolframLibraryData libData) {
return LIBRARY_NO_ERROR;
}

/* Uninitialize Library */
DLLEXPORT void WolframLibrary_uninitialize( WolframLibraryData libData) {
return;
}

DLLEXPORT int converter_TT_T(WolframLibraryData libData, mint Argc, MArgument *Args, MArgument Res) {
MTensor result;

int err = LIBRARY_NO_ERROR;

MTensor valueTensor;
MTensor frequencyTensor;
mint *valueDataPtr;
mint *frequencyDataPtrHard;
mint *frequencyDataPtr;

mint *resultDataPtr;

mint valueDataDim;
mint frequencyDataDim;

valueTensor = MArgument_getMTensor(Args[0]);
frequencyTensor = MArgument_getMTensor(Args[1]);

valueDataPtr = libData->MTensor_getIntegerData(valueTensor);
frequencyDataPtrHard = libData->MTensor_getIntegerData(frequencyTensor);
frequencyDataPtr = frequencyDataPtrHard;

valueDataDim = * libData->MTensor_getDimensions(valueTensor);
frequencyDataDim = * libData->MTensor_getDimensions(frequencyTensor);

if(valueDataDim != frequencyDataDim) goto error_label;

mint iiii;
mint total = 0;

for(iiii = 0; iiii < valueDataDim; iiii++)
{
total += *frequencyDataPtr;
frequencyDataPtr++;
}

err = libData->MTensor_new(MType_Integer, 1, &total, &result);
if(err) goto error_label;

resultDataPtr = libData->MTensor_getIntegerData(result);

frequencyDataPtr = frequencyDataPtrHard;

mint jjjj;
mint freq;

for(iiii = 0; iiii < valueDataDim; iiii++)
{
jjjj = 1;
freq = *frequencyDataPtr;
while(jjjj <= freq){
*resultDataPtr = *valueDataPtr;
resultDataPtr++;
jjjj++;
}

valueDataPtr++;
frequencyDataPtr++;
}

libData->MTensor_disown(valueTensor);
libData->MTensor_disown(frequencyTensor);

MArgument_setMTensor(Res, result);
return err;

error_label:
libData->MTensor_disown(valueTensor);
libData->MTensor_disown(frequencyTensor);
if(!err) err = 1;
return err;

}


This function can be linked to the kernel as follows. Save the code above (and nothing more, you don't need a function main or something like that) in a file name.c at the path path (in a folder to which path points). Then execute the following code, after filling in the first two lines.

path = (*input your path here*)   ;
cFileName = (*input the name of your file (example: "name.c") here *)   ;

libraryName = "libraryName"

<< SymbolicC
<< CCodeGenerator
<< Developer
SetDirectory[path];

(*if you execute the command CreateLibrary below more than once, make sure to specify a
new libraryName *)

lib = CreateLibrary[{cFileName}, libraryName] (*no extension needed for libraryName*)

converterLL =
LibraryFunctionLoad[libraryName,
"converter_TT_T", {{Integer, 1, "Shared"}, {Integer, 1,
"Shared"}}, {Integer, 1}]


To test if the function has loaded successfully, you can now simply try feeding it some data

converterLL[{1, 2, 3, 4, 5, 6} // ToPackedArray, {1, 2, 1, 1, 1, 2} //
ToPackedArray]


which should evaluate to

{1, 2, 2, 3, 4, 5, 6, 6}

Note that the lengths of the arrays that are given as arguments to converterLL should be of equal length. Otherwise an error is thrown corresponding to err = 1 in LibraryLink. err = 1 is supposed to correspond to a type error, so don't be fooled by this.

Compiled function

The compiled function is really similar to the function written in C. This function does not calculate the total of the list of frequencies, unlike the function written in C. In C I access arrays using pointers, whereas here I use Part, e.g. in factors[[jjjj]]. Compiling with CompilationTarget->"C" makes this about 4 times as fast the result without this option.

cfu =
Compile[
{{primeTimes, _Integer, 1}, {factors, _Integer,
1}, {tot, _Integer}, {nPrimes, _Integer}}
,
Block[{res, kkkk, fac},
res = ConstantArray[0, tot];
kkkk = 0;
Do[
fac = factors[[jjjj]];
Do[
kkkk++;
res[[kkkk]] = fac
,
{primeTimes[[jjjj]]}
]
,
{jjjj, nPrimes}
];
res
]
,CompilationTarget-> "C"
]


Other methods

One of the functions using Span below has Part as a local variable in Block. This is not really necessary and it may cause problems when you are using dynamics. But I suppose it keeps things funky.

initWSpanList[] :=
(
occurrences = Accumulate@primeTimes;
tot = Last@occurrences;
spanList =
Span @@@
Transpose[{Prepend[Delete[occurrences, -1], 0] + 1,
occurrences}];
)

span1[] :=
Block[{occurrences, tot, spanList, res1, applyFoodRes1},
initWSpanList[];
res1 = ConstantArray[0, tot];
applyFoodRes1 = Transpose[{spanList, sortedUniquePrimes}];
Function[res1[[#1]] = #2] @@@ applyFoodRes1;
res1
];

span2[] :=
Block[{occurrences, tot, spanList, applyFoodRes1},
initWSpanList[];
res2 = ConstantArray[0, tot];
ReleaseHold@
Block[
{res2, Part},
Hold[Set][Hold@Evaluate[res2[[#]] & /@ spanList],
sortedUniquePrimes]
];
res2
];


Functions for tidyness and comparison

inner[] := Inner[ConstantArray, sortedUniquePrimes, primeTimes, Join]

compiled[] := cfu[primeTimes, sortedUniquePrimes, Total@primeTimes,
Length@sortedUniquePrimes];

libLink[] := converterLL[sortedUniquePrimes, primeTimes];


Timing Comparisons

<< Developer
(res1 = span1[]) // Timing // First
(res2 = span2[]) // Timing // First
(res3 = inner[]) // Timing // First
(res4 = compiled[]) // Timing // First
(res5 = libLink[]) // Timing // First

TrueQ[res1 == res2 == res3 == res4 == res5]
PackedArrayQ /@ {res1, res2, res3, res4, res5}
{Length@res1, Total@primeTimes}


0.497182
0.410232
0.152209
0.020913
0.003353
True
{True, True, True, True, True}
{1100332, 1100332}

-
Am I really dumb or is this an answer to another question? – s0rce Nov 28 '13 at 16:31
@s0rce ah well you should read vals == sortedUniquePrimes and counts == primeTimes. Then you will see that my res3 is generated by halirutans code. I'm sorry it was indeed going to be a separate self answered Q&A, but then I found this question and I felt it was too similar to make a new Q&A. The data was generated with a different idea in mind, but really its the same thing. Maybe my adaptations were insufficient. – Jacob Akkerboom Nov 28 '13 at 16:43
Another note: We can probably avoid two rewrites of the entire array if we use librarylink, as we do not have to initialize all the elements of the tensor to 0 (which ConstantArray does do). – Jacob Akkerboom Nov 28 '13 at 17:56
@s0rce I have updated the answer, perhaps you wanna have another go at it? – Jacob Akkerboom Nov 29 '13 at 16:45
The LibraryLink function is also reasonably efficient with memory, there is somehow some smallish overhead cost of memory that you do not get back. But that does not scale with the size of the input. Also it does not use more memory than the size of the final output plus the size of inputs. In particular inputs and outputs are shared with Mathematica. – Jacob Akkerboom Dec 9 '13 at 14:54

One interpretation of this question is to find a data sequence that, on average, has the same distribution as the given histogram. This is easily accomplished. Using the OPs example,

RandomChoice[{1, 2, 3}/6 -> {5, 7, 4}, 6]


gives six numbers that have the same average occurrences as the original. An advantage of this is that it is easy to generate much longer sequences with the same distribution:

RandomChoice[{1, 2, 3}/6 -> {5, 7, 4}, 100]

-